函数的大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.

我试图找到函数的复杂度BigO。因此，对于嵌套列表，它应该是O（n ^ 2），但是它也具有一个条件语句，该条件语句将遍历列表中的所有元素，所以它将是O（n ^ 3）吗？

Answer 1

如果条件中的some code遍历列表中的所有元素，并且some code运行的次数与lst中元素的数量成比例，则时间复杂度将为O（n < [3）。

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

2）。