Was sind die großen O Notation für diese for-Schleifen?

Question

Ich beende eine Aufgabe für meine Klasse, dieser spezielle Abschnitt beinhaltet eine "Analyse" der Laufzeit für mehrere For-Schleifen. Der Ausbilder gab an, dass er eine Big Oh Notation-Antwort möchte.

ich auf dem Fundament baue die Zeit Gesamtlauf basiert auf:

1)The cost of executing each statement 
2)The frequency of execution of each statement 
3)The idea of working from "inside and out", specifically starting from inner loops. 

Ich weiß, dass:

total = 0; 

    for (int i = 0; i < n;i++){ 
    total++; 
} 

Antwort: O (N) seinen Lauf linear.

for (int i = 0; i < n;++i) 
    for (int j = 0; j < n;++j) 
    total++; 

Antwort: O (N^2), uns interessiert nur, wie groß N wächst.

ich auf

for (int i = 0;i < n;++i) 
    for (j=0;j < n * n;++j) 
    ++total; 

und

for (i = 0;i < n;++i) 
    for (j = 0; j < i;++j) 
    ++total; 

Und last but not least, ich gehe davon aus von meinem Lehrbuch, das alle Triple-verschachtelten Schleifen an N^3 Mal laufen bin verwirrt?

Answer 1

Sie können Ihre Algorithmen Sigma-Notation, analysieren die Anzahl der Iterationen durch die innere for-Schleife Ihrer Algorithmen laufen zu zählen/erweitern:

Wo T_a deckt

for (i = 0; i < n; ++i) 
    for (j = 0; j < n * n; ++j) 
     ++total; 

und T_b:

for (i = 0; i < n; ++i) 
    for (j = 0; j < i; ++j) 
     ++total; 

---

Schließlich ist ein Hinweis auf Ihre Frage:

„Und last but not least, die ich von meinem Lehrbuch gehe davon aus, dass alle Triple-verschachtelten Schleifen in N^3 Zeit laufen“

Dies ist nicht wahr: Es hängt davon ab, wie die Iterierte sowie begrenzt erhöht wird in der Signatur jeder Schleife. Vergleiche z.B. mit der inneren Schleife in T_a oben (begrenzt durch n^2, aber einfach erhöht durch 1 in jeder Iteration) oder z.B. the algorithm analyzed in this answer, oder, für einen etwas komplizierteren Fall, the single loop analyzed in this answer.