python - 函数的大 O 复杂度

Question

def x(lst):
   z = 0
   for a in range(len(lst)):
       for b in range(len(lst)):
           mx = lst[0][0]
           if mx > z:
               z = mx           
   return z.

我试图找到函数的复杂性 Big O。所以对于嵌套列表，它会是 O(n^2)，但它也有一个条件语句会遍历列表中的所有元素，那么它会是 O(n^3) 吗？

标签： pythontime-complexitybig-onested-lists

Answer 1

如果some code在条件中遍历列表的所有元素，并且some code运行的次数与 中的元素数量成正比lst，那么时间复杂度将为 O(n ³ )。

如果条件评估为真的次数与不成比例，len(lst)则时间复杂度会更低。例如，如果some code运行的次数是恒定的而不管列表的大小，那么时间复杂度将仅为 O(n ² )。