Was ist die zeitliche Komplexität meiner Funktion?

Question

Gestartet um Komplexität zu studieren, ich bin mit diesem zu kämpfen:

void what(int n) { 
    int i; 
    for (i = 1; i <= n; i++) { 
     int x = n; 
     while (x > 0) 
      x -= i; 
    } 
} 

Nun, die ersten for-Schleife deutlich O(n) ist. Die erste Iteration ist O(n), die zweite ist O(n/2) .. und so log(n) mal ich denke? Das bedeutet O(n) * O(log(n)) = O(n * log(n)) complexity. Habe ich das richtig verstanden?

Edit: (kein Duplikat) Ich weiß, was Big O ist. Ich habe in einem konkreten Fall die richtige Bewertung verlangt.

Answer 1

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

Für jede Iteration läuft die innere Schleife n/i mal.

Die Gesamtzahl der Durchläufe ist:

n + n/2 + n/3 + ... + n/n 

Asymptotisch (ohne Berücksichtigung Integer-Arithmetik Rundung), vereinfacht dies als

n * (1 + 1/2 + 1/3 + ... + 1/n) 

Diese Reihe lose gegen n * log(n) konvergiert.

Daher ist die Komplexität O (N.log (N)) wie erwartet.

Answer 2

Die erste innere Schleife läuft n mal
Die zweite innere Schleife läuft n/2 mal
Die dritte innere Schleife n/3 Zeiten läuft
.. Der letzte einmal

n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n) So läuft.

Dies ist n multipliziert mit der Summe der harmonischen Reihen, die keine schöne geschlossene Formdarstellung haben. Aber wie gezeigt here ist es O(log(n)). Also insgesamt ist der Algorithmus O(n log(n))

Answer 3

Dies wird durch Tests und Grafiken versucht. Das Diagramm log2 vs log2 sieht ziemlich linear aus. Etwas zwischen mehr als linearem O (n) und weniger als O (n * log (n)). "Zeichnen" Sie Ihre eigene Schlussfolgerung.

[Bearbeiten]

die mathematischen Formeln abgeleitet, die O() berechnet wird, eine obere Grenze von O (N · log (n)). Das verwendet "Brüche von Schleifeniterationen", die die Zählung um einen Bruchteil und nicht um 1 erhöhen. Wenn n 6 ist, ist die Iterationszahl 6 + 3 + 2 + 1,5 + 1,2 + 1 = 14,7 Schleifen eher als tatsächlich 6 + 3 + 2 + 2 + 2 + 1 = 16. Dieser Unterschied ist relativ weniger signifikant, da n zunimmt das etwas weniger als O (n * log (n)) Wachstum. Also, indem wir Code nicht ignorieren, verwenden wir ganzzahlige Mathematik, wir haben eine viel schwierigere Frage.

---

unsigned long long what(int n) { 
    unsigned long long cnt = 0; 
    int i; 
    for (i = 1; i <= n; i++) { 
    int x = n; 
    while (x > 0) { 
     x -= i; 
     cnt++; 
    } 
    } 
    return cnt; 
} 

void wtest(int n) { 
    unsigned long long cnt = what(n); 
    printf("%d %llu\n", n, cnt); 
    fflush(stdout); 
} 

void wtests(void) { 
    int i = INT_MAX/2 + 1; 
    while (i > 0) { 
    wtest(i); 
    i /= 2; 
    } 
} 

int main(void) { 
    wtests(); 
    return 0; 
} 

Output

1073741824 23567395117 
536870912 11411566988 
268435456 5519718329 
134217728 2666826555 
67108864 1286897093 
33554432 620190504 
16777216 298466265 
8388608 143418602 
4194304 68802063 
2097152 32947406 
1048576 15746897 
524288 7510048 
262144 3573331 
131072 1695816 
65536 802493 
32768 378537 
16384 177921 
8192 83286 
4096 38803 
2048 17973 
1024 8275 
512 3782 
256 1713 
128 765 
64 337 
32 145 
16 61 
8 24 
4 9 
2 3 
1 1 

Answer 4

Als Alternative verwenden, um eine variable Substitution y = n - x von Sigma-Notation folgt die Anzahl der Iterationen der inneren while Schleife des Algorithmus zu analysieren, . die Anzahl der Iterationen durch 1 für Fälle

Die obigen Überschätzungen für jeden inneren While-Schleife, wo n-1 nicht ein Vielfaches von i ist, das heißt, wo (n-1) % i != 0. Wenn wir fortfahren, nehmen wir an, dass (n-1)/i eine ganze Zahl für alle Werte von i ist, und überschätzt daher die Gesamtzahl der Iterationen in der inneren while Schleife, die nachfolgend das kleinere oder gleiche Vorzeichen bei (i) enthält. Wir gehen mit der Notation Analyse Sigma:

, wo wir bei (ii), die n angenähert haben: th harmonic number durch das zugehörige Integral. Daher läuft Ihr Algorithmus asymptotisch in O(n·ln(n)).

---

Asymptotik Weggehen und die tatsächliche Wachstum des Algorithmus zu studieren, können wir die schönen Beispieldaten exakter (n,cnt) (wo cnt ist die Anzahl der inneren Iterationen) Paare von @chux (siehe seine Antwort) verwenden und vergleichen mit der geschätzten Anzahl von Iterationen von oben, dh n(1+ln(n))-ln(n). Es ist offensichtlich, dass die Schätzung harmonisch mit der tatsächlichen Zählung harmoniert, siehe die folgenden Diagramme oder this snippet for the actual numbers.

---

Schließlich ist zu beachten, dass, wenn wir n->∞ in der Summe über 1/i oben lassen, ist die resultierende Serie ist die infinite harmonic series, das ist merkwürdigerweise divergent. Der Beweis für letzteres macht Gebrauch von der Tatsache, dass in unendlicher Summe von Nicht-Null-Termen natürlich selbst unendlich ist. In der Praxis ist jedoch für eine ausreichend große, aber nicht unendliche n, ln(n) eine geeignete Approximation der Summe, und diese Divergenz ist hier für unsere asymptotische Analyse nicht relevant.

---