循環的時間複雜度是多少？

Question

def f2(lst): 
    i = len(lst) 
    while i>0: 
    for j in range(i, i+10**8): 
     for k in range(i): 
      print(k) 
     i -= 2 

什麼是時間複雜度？而將運行n/2次，但其餘的呢？

Answer 1

答案是O(n^2)。

第一個循環是〜n，第二個循環是恆定時間，第三個循環是〜n。

Answer 2

正如你所說，while循環將迭代n/2次，因此具有O(n)複雜性。

第一個for循環（for j in range(i, i+10**8)）具有恆定的運行時間O(1)。

第二個for循環具有複雜性O(n)並且將執行n+n^2通過。

這使代碼O(n^2)複雜