Worst time Komplexität (Big O) für 1 für Schleife

Question

Also verstehe ich die meisten Komplexitätsprobleme; Das verwirrt mich jedoch.

Wenn die zweite Anweisung in der for-Schleife wie folgt ist (i * i < n), was wäre tre Big O für die Schleife? Wie wäre es berechnet?

for (i = 1 ; i * i < n ; i++) 

Answer 1

Unter der Annahme, dass n ein Proxy für die Größe des Eingangs ist (und dass der Code nur die Schleife auszuführen, einmal für jedes verarbeitbares Element des Eingangs, und es gibt keine andere Eingabeelement-Auswahllogik).

i * i < n 
    i^2 < n 
    i < Sqrt(n) 

Also, eine Zeitkomplexität von O(Floor(Sqrt(n))).

Lasst uns ein Beispiel mit n = 10 sehen (die Tabelle zeigt den Zustand der Variablen am Ende jeder Iteration, genau in dem Moment vor i++ ausgewertet wird und die i * i < n Test durchgeführt wird).

Iteration, i, i * i, n 
     1, 1,  1, 10 
     2, 2,  4, 10 
     3, 3,  9, 10 
     4, 4,  16, 10 -- 16 > 10, abort loop 
     5, 5,  25, 10 -- for illustrative purposes 

(Beachten Sie, dass, wie die i^2 < 10 Prüfung vor durchgeführt wird, die Schleife ausgeführt wird, Iteration 4 nicht ausgeführt wird, so wird die Schleife 3 Mal durchgeführt werden. Die genaue Quadratwurzel von 10 ist 3.1622... aber Iterationszählungen sind 0-basierte natürliche Zahlen, verwenden Sie also Floor.).

Answer 2

i*i<n 

als

i<sqrt(n) 

So seine acutally O(sqrt(n))