Wie hoch ist die zeitliche Komplexität meiner Funktion? [duplicate]

Ich habe angefangen, mich mit Komplexität zu beschäftigen, ich kämpfe mit diesem:

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

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

Bearbeiten: (kein Duplikat) Ich weiß, was Big O ist. Ich habe um die richtige Bewertung im konkreten Fall gebeten.

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

Bei jeder Iteration werden die inneren Schleifen ausgeführt n / i mal.

Die Gesamtzahl der Läufe beträgt:

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

Asymptotisch (ohne arithmetische Ganzzahlrundung) vereinfacht sich dies als

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

Diese Reihe konvergiert lose in Richtung n * log(n).

Daher die Komplexität O(N.log(N)) wie Sie es erwartet haben.

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

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

Dies wird n multipliziert mit der Summe der harmonischen Reihen, die keine schöne Darstellung in geschlossener Form hat. Aber wie hier gezeigt ist es so O(log(n)). Insgesamt ist der Algorithmus also O(n log(n))

Verwenden Sie alternativ eine Variablensubstitution y = n - x gefolgt von der Sigma-Notation, um die Anzahl der Iterationen des inneren zu analysieren while Schleife Ihres Algorithmus.

Das Obige überschätzt für jede innere While-Schleife die Anzahl der Iterationen um 1 für Fälle wo n-1 ist kein Vielfaches von idh wo (n-1) % i != 0. Im weiteren Verlauf gehen wir davon aus (n-1)/i ist eine ganze Zahl für alle Werte von iwodurch die Gesamtzahl der Iterationen im Inneren überschätzt wird while Schleife, anschließend mit dem Kleiner- oder Gleichheitszeichen at (i) unter. Wir fahren mit der Sigma-Notationsanalyse fort:

wo wir, an (ii)haben die angenähert n:th harmonische Zahl durch das zugehörige Integral. Daher läuft Ihr Algorithmus ein O(n·ln(n))asymptotisch.

Wenn wir das asymptotische Verhalten verlassen und das tatsächliche Wachstum des Algorithmus untersuchen, können wir die schönen Beispieldaten von Exact verwenden (n,cnt) (wo cnt ist die Anzahl der inneren Iterationen) Paare von @chux (siehe seine Antwort) und vergleichen Sie mit der geschätzten Anzahl der Iterationen von oben, dh n(1+ln(n))-ln(n). Es ist offensichtlich, dass die Schätzung gut mit der tatsächlichen Zählung harmoniert, siehe die Diagramme unten oder dieser Ausschnitt für die tatsächlichen Zahlen.

Beachten Sie schließlich, dass, wenn wir lassen n->∞ in der Summe vorbei 1/i oben ist die resultierende Reihe die unendliche harmonische Reihe, die merkwürdigerweise divergent ist. Der Beweis für letzteres macht sich die Tatsache zunutze, dass in unendlicher Summe von Nicht-Null-Termen natürlich selbst unendlich ist. In der Praxis jedoch für a ausreichend groß, aber nicht unendlich n, ln(n) ist eine angemessene Annäherung an die Summe, und diese Divergenz ist für unsere asymptotische Analyse hier nicht relevant.

Versuchen Sie dies durch Tests und Grafiken. Das Diagramm log2 vs. log2 sieht ziemlich linear aus. Etwas zwischen mehr als linearem O(n) und weniger als O(n*log(n)). “Ziehen” Sie Ihr eigenes Fazit.

[Edit]

Unter Verwendung der mathematisch abgeleiteten Formeln ist das berechnete O() eine Obergrenze von O(n * log(n)). Das verwendet “Bruchteile von Schleifeniterationen”, die die Anzahl um einen Bruchteil und nicht um 1 erhöhen. ZB When n 6 ist, ist die Anzahl der Iterationen 6 + 3 + 2 + 1,5 + 1,2 + 1 = 14,7 Schleifen statt tatsächlich 6 + 3 + 2 + 2 + 2 + 1 = 16. Dieser Unterschied ist relativ weniger signifikant als n steigt, also das etwas weniger als O(n * log(n)) Wachstum. Wenn wir also nicht ignorieren, dass Code Integer-Mathematik verwendet, haben wir eine viel herausforderndere 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;
}

Ausgabe

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