python中opper的渐近复杂性

Question

我正在研究python中函数的复杂性，我不确定这里有两个，一个是因为我认为它是无限循环，另一个是python内置的非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.exo（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）时间函数