В части ArrayList есть пять статей, и для анализа вводится временная сложность,Настоятельно рекомендуется прочитать по порядку, эта статья является третьей статьей, первые две статьи:
1,Инициализация ArrayList - столбец Java те вещи
2,Принцип расширения массива, лежащий в основе ArrayList - Java те вещи, столбец
Недавно я просматривал область комментариев. Все хотят понять HashMap. Не волнуйтесь. Чтобы полностью понять внутреннюю реализацию HashMap, нам все еще нужны некоторые базовые знания. С этими базовыми знаниями мы можем лучше понять HashMap. На самом деле, мы неосознанно вошли в дверь структуры данных.Чтобы каждый мог лучше понять последующие статьи в будущем, мы сначала представляем эту статью.временная сложностьэто понятие.
Это все еще объект Person, добавляющий возраст атрибута
Создайте массив и поместите в массив объект 10 Person, старые правила, мы на карте:
Если у нас есть такое требование, мы хотим узнать возраст августа в группе, я думаю, каждый напишет код, чтобы найти его:
Вам нужно выполнить цикл 6 раз, чтобы получить объект Person из массива.
В это время подошел одноклассник Сяо Мин и сказал: «О, я знаю, что Суббота находится на пятой позиции в группе (индекс массива 5), не нужно зацикливаться, мы просто найдем его напрямую.
Не нужно зацикливаться, получите объект Person один раз:
Независимо от того, сколько элементов в массиве, время чтения элементов и их сравнения всегда одинаково каждый раз. Предположим, что это время равно K. В приведенном выше примере мы просматриваем массив в цикле для поиска пользователя и мы делаем цикл 6 раз перед поиском.Для пользователя время равно 6*К.С точки зрения эффективности первое в 6 раз быстрее второго, но это утверждение не имеет смысла, так как на практике массив может иметь 100 элементов , и эта "неделя "Восьмерка"" может быть в первой позиции массива, а может быть и в последней позиции.
На самом деле мы используем для расчета длины времени, общей единицей являются часы, минуты, секунды и т. д., также нам нужна мера для расчета эффективности алгоритма в этом примере, в информатике,Эта мера известна как обозначение «большой O»..
Когда мы знаем местоположение элемента, мы можем получить доступ к элементу за один шаг.На этот раз время K, а временная сложность отмечена как O (1) в нотации большого O.К опущен. При поиске элемента в массиве мы не знаем, где находится элемент в массиве.Предполагая, что длина массива равна n, возможно, что элемент просто зацикливается один раз в позиции, где индекс массива 0 (первая позиция), совпадение, временная сложность O(1). Также возможно, что нам нужно выполнить цикл n раз, чтобы сопоставить значение в позиции, отмеченной n-1 в массиве (последняя позиция).Временная сложность составляет O (n), а среднее значение равно n/2 в соответствии с расчет вероятности, т.Средняя сложность времениO (n / 2), но мы должны учитывать не только среднее значение, мы должны учитыватьХудшая ситуация, то есть предполагая, что каждый соответствующий элемент находится в последней позиции массива, потому чтохудший случайэтоГарантия безотказной работы, время выполнения не будет больше.Если мы не укажем его, то время выполнения, которое мы упомянули, является временем выполнения в худшем случае, то есть для поиска элемента в массиве временная сложность составляет O (n);
в массиве длины n:
Чтобы получить доступ к элементам напрямую через индексы, временная сложность равнаO(1).
Когда вам нужно зациклиться, чтобы найти элементы, временная сложностьO(n).
В следующей главе мы проанализируем исходный код ArrayList, чтобы удалить элементы, проанализировать временную сложность ArrayList, а затем разберемся в преимуществах и недостатках ArrayList.
Предыдущий:Принцип расширения массива, лежащий в основе ArrayList - Java те вещи, столбец
Далее: для продолжения
Примечание. Эта колонка была впервые опубликована в общедоступной учетной записи: sayayJava. Все примеры кодов были загружены на официальный аккаунт, обратите внимание на загрузку, если вам это нужно.
Если вам нравится эта серия статей,Пожалуйста, поставьте лайк или поделитесь для меня, ваша поддержка является движущей силой для меня, чтобы продолжать. Вы также можете оставить сообщение в области комментариев, чтобы узнать, что вы хотите знать. Если у вас есть возможность, эта колонка объяснит это. Наконец, не забудьте заплатить внимание ко мне.
Перепечатка приветствуется, но с указанием "автора" и "оригинального адреса". Пожалуйста, сохраните этот абзац в тексте для перепечатки, спасибо за уважение авторских прав. Для коммерческого воспроизведения или публикации, пожалуйста, свяжитесь с автором для получения разрешения.