Laufzeit dieser Python-Funktion

Question

def loopy_loop(n): 
    for i in range(n): 
    for j in range(i): 
     if j*j > i: 
     break 

Dabei ist n eine positive Ganzzahl.

Sagen wir, ich nehme n = 10

Die äußere Schleife läuft n-mal sicher (n = 10 mal) Die innere Schleife auf der Grundlage der Werte laufen.

• n = 0, ist die innere Schleife läuft 0 mal

• n = 1, die innere Schleife läuft einmal

• n = 2, die innere Schleife ausgeführt wird 3 mal

• n = 3, die innere Schleife läuft 4 Mal (bis j = 3 und 9> 3)

• n = 4, die innere Schleife läuft 4 mal so gut

• und so weiter, bis n = 9, wo es 5 mal läuft

Ich habe Schwierigkeiten alles zusammen setzen die Laufzeit mit O-Notation auszudrücken. Gibt es einen Set-Algorithmus, der mir für dieses spezifische Code-Snippet helfen könnte?

Answer 1

Die äußere Schleife läuft n mal.

Die innere Schleife sqrt(i) mal läuft (weil, wenn i gegeben ist es stoppt, wenn j**2i erreicht), aber i wächst (grob) wie n (n//2 Durchschnitt)

Die Komplexität O(n**1.5) (n mal Quadratwurzel n ist

)

genauere Schätzung:

def loopy_loop(n): 
    counter=0 
    for i in range(n): 
     for j in range(i): 
      counter+=1 
      if j*j > i: 
       break 
    return counter,int((n)*(n//2)**0.5) 

print(loopy_loop(5)) 
print(loopy_loop(10)) 
print(loopy_loop(100)) 
print(loopy_loop(1000)) 
print(loopy_loop(15000)) 

Ergebnis (Anzahl gegen Schätzung):

(10, 7) 
(31, 22) 
(810, 707) 
(22579, 22360) 
(1247250, 1299038)