Laufzeitanalyse: Korrigieren Sie meine Beispiele auf Warum diese Schleifen haben O (log n) Zeit Komplexität

Question

Ich Analyse von Schleifen zu tun, habe diese folgenden Schleifen:

for (int i = 1; i <=n; i *= c) { 
     // some expressions 
    } 

for (int i = n; i > 0; i /= c) { 
     // some expressions 
    } 

Ich verstehe, dass die Schleife Wachstumsrate log ist n (base c) Aber ich bin stecken, während einige Testbeispiele tun, wie unten:

Schleif-1: wenn c = 2 und n = 8, dann

Schleife läuft gilt für i = 1,2 , 4,8 (4 mal) ABER log 8 = 3? [4 sollte sein]

Schleif-2: wenn c = 2 und n = 8, dann

Schleife für i = 8,4,2,1 stimmt mit (4-mal) BUT log 8 = 3 ? [sollte 4 sein]

Wo ich die Fehler gemacht habe. bitte helfe mir, die Ergebnisse mit Time Rate Log n zu vergleichen. Danke

Answer 1

O-Notation ist immer eine Annäherung, oder besser eine Worst-Case-Grenze. Zum Beispiel O(logN)=O(logN+X), wenn X eine Konstante ist. In Ihrem Beispiel sind die genauen Iterationen Ihrer for-Schleife logN+1, was bedeutet, ist O(logN+1)=O(logN).

Answer 2

Hier ist die beste Antwort von einer akademischen Referenz:

Quelle: http://faculty.kfupm.edu.sa/ics/jauhar/ics202/Unit03_ComplexityAnalysis1.ppt