写这段代码有困难，复杂度为O（N）

Question

任务：

given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in 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

“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是集合（不是列表或数组.array)，平均为O（N）。 请参见此处的详细信息：https://wiki.python.org/moin/TimeComplexity或Complexity of *in* operator in Python。你知道吗

Answer 3

您正在对列表中所有肯定的项进行O(N)遍历。 在每一次迭代中，您都会让python通过询问“j in A”，在列表中进行另一次O(N)遍历？它可能遍历A的所有元素，搜索j。 所以你的复杂性变成：O(N) * O(N) = O(N^2)