Худшая временная сложность линейного поиска O (n)

Question

Я пытаюсь написать отчет, в котором я оцениваю временную сложность разработанного мною алгоритма, я точно знаю, что это сложность O (n).Из того, что я получил из Википедии, лучший случай будет O (1), если я правильно понял, это означает, что лучший случай - это когда ArrayList, который я использую, содержит только один элемент, но я не получаю наихудший случай полностью, что означает «O (1) итеративный» и как это может произойти?

Answer 1

В комментарии вы пишете:

В моем случае я не ищу какой-то конкретный элемент списка, но мне нужно проверить, является ли атрибут каждого отдельного элемента истинным или ложным.

Это не линейный поиск.Поиск (линейный или другой) отвечает на вопрос «есть ли хотя бы один соответствующий элемент».Ваш вопрос «соответствуют ли все элементы».

Мне всегда нужно было бы подумать, что весь список от первого до последнего элемента, так что будет худший и лучший случай.

В лучшем случае все еще O (1).Если вы обнаружите, что одним из атрибутов элемента является false, вы можете немедленно прервать сканирование.Наилучший случай, когда это происходит для первого элемента ....

Учтите это.Проверка того, что «все элементы истинны» эквивалентна проверке, что «НЕ (некоторый элемент ложен)».

Answer 2

Причина в том, что O (1) лучший случай, это НЕ ПРОСТО для списка с 1 элементом (хотя в этом сценарии это также будет).Представьте, что у вас есть список из 10 чисел.

[44,6,1,2,6,10,93,187,33,55]

Допустим, мы запускаем линейный поиск и ищем целое число 44. Поскольку это первый элемент в списке, наша сложность по времени равна O (1),В лучшем случае, потому что нам нужно только найти 1 элемент из всего списка, прежде чем мы найдем то, что ищем.

Давайте рассмотрим вариант этого списка.

[55,6,1,2,6,10,93,187,33,44]

В этом случае мы поменялись местами первые и последние цифры.Поэтому, когда мы запустим линейный поиск целого числа 44, это будет сложность по времени O (n), наихудший случай, так как нам нужно пройти весь список из n элементов, прежде чем мы найдем желаемый элемент (если он вообще существует всписок, в нашем случае это делает).

Что касается "O (1) итеративного" в Википедии, я бы не позволил этому сбить вас с толку.Также обратите внимание, что это относится к сложности space на странице Википедии, а не к производительности по времени.Нам не нужно никакого дополнительного пространства для хранения чего-либо во время линейного поиска, мы просто сравниваем желаемое значение (например, 44 в примере) с элементами в массиве один за другим, поэтому мы имеем пространственную сложность O (1).

РЕДАКТИРОВАТЬ: на основе вашего комментария:

В моем случае я не ищу элемент списка в частности

Имейте в виду«Линейный поиск» - это особый алгоритм с конкретной целью поиска определенного элемента в списке, который вы упоминаете, это НЕ то, что вы пытаетесь сделать.Похоже, вы ищете Линейный поиск.Линейный поиск задается массивом / списком и желаемым элементом.Он вернет индекс, где искомый элемент находится в списке, при условии, что он существует в списке.

Мне всегда нужно было бы идти, думая весь список от первого до последнего элемента

Из вашего комментария я полагаю, что вы всегда пытаетесь пройти список от начала до конца, всегда.Это всегда будет O (N), так как вы всегда просматриваете весь список.Рассмотрим простой пример Python:

L1 = [1,2,3,4,5,6,7,8,9,10]  #Size n, where n = 10

for item in L1:
    print(item)

Это просто напечатает каждый элемент в списке.Наш список имеет размер n.Таким образом, временная сложность обхода списка составляет O (n).Это применимо, только если вы хотите каждый раз просматривать весь список.