Worst-Case-Komplexität für diese Python-Code

Question

Was die ungünstigste Zeit Komplexität der folgenden ist:

def fun(n): 
    count=0 
    i=n 
    while i>0: 
     for j in range(0,i): 
      count+=1 
     i/=2 
    return count 

Answer 1

Worst case Zeitkomplexität, wenn n wirklich große ganze Zahl ist.

O (log (n) * n) (Erraten).

So kam ich zu meiner Schlussfolgerung.

while i>0: 
     ... 
     i/=2 

Dies wird log (n) mal ausgeführt, weil es jedes Mal halbiert wird, wenn es ausgeführt wird.

for j in range(0,i): 

Dies wird n mal zuerst, n/2 mal das 2. mal, und so weiter. Also, für diese Linie Gesamtlaufzeit ist n + n/2 + n/4 .... 1 = (2n-1)

count+=1 

Dies ist ein preiswerter Betrieb so ist O (1).

Somit wird die Gesamtlaufzeit dieser Funktion O (log (n)) * O (2n-1), wenn n eine ganze Zahl ist. Vereinfacht wird O (log (n) * (n)).