python中O-Upper的渐近复杂度

Question

我正在研究python中函数的复杂性，我这里有两个我不确定，一个是因为我认为它是无限循环第二个是python中内置的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中需要平摊O(1)时间。这是因为字典实际上并不遍历它的所有元素来查找x，而是使用底层哈希映射数据结构。在Python中，向列表追加操作实际上也是一个常量时间操作。因此，f2实际上是一个O(n)时间函数。