写这段代码有困难，复杂度为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

“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。你知道吗