这个 python 函数的时间复杂度是多少？

Question

def hasPairWithSum(arr,target):
     for i in range(len(arr)):
         if ((target-arr[i])  in arr[i+1:]):
             return True

    return False

在python中，这个函数的时间复杂度是O(n)还是O(n^2)，换句话说'if ((target-arr[i]) in arr[i+1:])'这是不是另一个for循环？还有下面的函数呢，是不是也是O(n^2)，如果不是为什么：

def hasPairWithSum2(arr,target):
   seen = set() 
   for num in arr:
      num2 = target - num
      if num2 in seen:
         return True
      seen.add(num)
   return False

谢谢！

Answer 1

是 O(n^2)

第一个循环将运行 n 次，第二个循环将运行 (n-m) 每 n 次。所以整个事情将运行 n(n-m) 倍，即 n^2 - nm。知道 m 我们知道它的复杂度为 O(n^2)

但如果这对某些事情至关重要，您可能会咨询更擅长此方面的人。

Answer 2

第一个版本有 O(n²) 时间复杂度：

实际上 arr[i+1:] 已经创建了一个包含 n-1-i 元素的新列表，这不是一个常量时间操作。 in 运算符将扫描那个新列表，并且在最坏的情况下访问那个新列表中的每个值。

如果我们计算复制到新列表中的元素数量（arr[i+1），我们可以对外循环的每次迭代计算这些计数：

  n-1
+ n-2
+ n-3
+ ...
+ 1
+ 0

这是一个triangular number，等于n(n-1)/2，即O(n²).

第二个版本

第二个版本使用 set，平均时间复杂度为 O(n)。

这里没有列表切片，集合上的 in 运算符——与列表参数相反——具有平均常量时间复杂度。所以现在循环中的每个动作都有一个（平均）常数时间复杂度，使算法的平均时间复杂度为 O(n).

根据 python docs，集合的 in 运算符的摊销最差时间复杂度为 O(n )。因此，对于 O(n²).

的算法，您仍然会得到最差的时间复杂度

这个 python 函数的时间复杂度是多少？

Whats time complexity of this python function?

python

algorithm

time-complexity

第二个版本