O-Upper python 的渐近复杂度

Question

我正在研究 python 中函数的复杂性，我有这两个我不确定，一个是因为我认为它是无限循环，第二个是在 [=21 上构建的 not in 方法=]:

1-函数f1接收一个正整数n和一个列表v。v大于n。

def f1(n, v): 
   b=n*n
   s=0
   while b > 1: 
      s += v[n]
      s += b
      b -= 2 
   return s

2-函数f2接收字典d和列表l。

def f2(d,l): 
   r = []
   for x in l:
      if x not in d:
         r.append(x)
return r

我正在研究“O-Upper”，O.ex O (n ^ 2) 是二次的。 这两个函数的复杂度是多少？

Answer 1

f1 包含一个执行 O(n²) 次的循环，它只执行常量时间操作.就像 EnderShadow8 解释的那样，这使得你的函数 O(n²).

f2 包含一个执行 O(n) 次的循环，其中 n 是 l 的长度。 由于 d 是一个 Python 字典，检查 x 是否在 d 中运行在 amortized O(1) time 中。这是因为字典实际上并不遍历其所有元素来查找 x，而是使用底层哈希映射数据结构。 附加到列表实际上也是 Python 中的常量时间操作。 因此，f2实际上是一个O(n)的时间函数。