проблемы при написании этого кода со сложностью O (N)

Question

Задача:

, учитывая массив A из N целых чисел, возвращает наименьшее положительное целое число (больше 0), который не встречается в A.

Мой код:

def search(A):
   j=1
   while j in A:
      j+=1;
   return j;  

Почему моя временная сложность O (N ^ 2)?

Answer 1

Предположим, ваш ввод имеет вид 1..N.

Затем ваш код выполнит N итераций, каждую из которых он потенциально проверяет по всей длине списка, чтобы увидеть, присутствует ли в списке текущее значение j. N итераций проверки всего списка длины N дает N * N = N ^ 2.

Это пример наихудшего случая, но мы не знаем, каким должен быть типичный ввод. Может быть, вы это знаете, а может и нет. Простой и оптимальный в худшем случае способ сделать это - отсортировать список, а затем найти первый «пробел» между элементами в вашем списке. Как то так:

def my_search(A):
   A = [i for i in sorted(A) if i > 0]  # Gets rid of <1 values as well
   min_pos_val = 1
   for val in A:
      if val > min_pos_val:
         return min_pos_val
      min_pos_val += 1
   return min_pos_val

Answer 2

Вы делаете O(N) обход потенциально всех элементов в списке, которые являются положительными. В каждой итерации вы позволяете python делать еще один O(N) обход списка, спрашивая 'j in A'? который потенциально проходит через все элементы A, ища j. Итак, ваша сложность становится: O(N) * O(N) = O(N^2)

Answer 3

Оператор "in" - O (N). И "while" - это O (возвращаемое значение).

[править] Позвольте мне подробно описать это: ваш код эквивалентен

j = 1
while True:     # is O(the returned j)
   if j in A:   # is O(N), bec. has to go through the whole array
      j += 1
   else: 
      return j

Так что в худшем случае ваш алгоритм действительно O (N ^ 2). В лучших случаях (например, если 1 не в A), алгоритм равен только O (N).

Если A является множеством (не списком и не массивом. Массивом), это будет O (N) в среднем . Подробности смотрите здесь: https://wiki.python.org/moin/TimeComplexity или Сложность оператора * in * в Python .