Algorithmus Zeit Komplexität: i/= 2 in Schleifen

int fun(int n) { 
    int count = 0; 
    for (int i = n; i > 0; i /= 2) 
     for (int j = 0; j < i; j++) 
      count += 1; 
    return count; 
}

Ich bin ein sehr neues zu der Zeit komplexe Berechnungen. Für diesen Algorithmus bekomme ich die Antwort zu O (nlogn), aber die Antwort ist offensichtlich O (n).Algorithmus Zeit Komplexität: i/= 2 in Schleifen

Meine Logik war die äußere Schleife hat eine exponentielle Abnahme und wird log_base2_ (N) mal auftreten. Die innere Schleife wird insgesamt N mal laufen, wenn sie eine geometrische Summe wird (erste Iteration ist N/2 mal, dann N/4, dann N/8 ...). Wenn ich diese zusammensetze und sie als Ergebnis der verschachtelten Schleife multipliziere, dann komme ich an O (NlogN). Fehle ich etwas offensichtlich?

Quelle

2017-09-13 user6142489

Die äußere Schleife würde insgesamt log (n) mal laufen. Nun, wenn Sie beobachten die innere Schleife es erstes Mal, es n-mal ausgeführt wird, neben n/2-mal und so weiter, so macht es die Serie

n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)

die Summe hierfür wäre (2 * n), Das heißt, es ist O (n)

Daher ist die Zeit Komplexität O (n) seit äußere Schleife läuft O (logn) mal und innere Schleife läuft O (n) mal.

Es ist nicht O (n log n), da die innere Schleife nicht jedes Mal nicht nehmen n Schritte unternommen, um die Summe aller Schritte in der Tat würde O (n)

Quelle

2017-09-13 11:03:03 marvel308

Dies ist hilfreich sein. Ich glaube, ich habe die Gesamtzahl der Operationen mit der Laufzeit verwechselt. Wenn ich Ihren Punkt richtig verstehe, ist die Zeitkomplexität die schlechtere der beiden Schleifen, in diesem Fall O (n). – user6142489

@ user6142489 im Allgemeinen ist es nicht die schlechteste der beiden Schleifen, sondern die Gesamtzahl der Iterationen der innersten Schleife. Wie wir in dieser Antwort ausgeführt haben, müssen wir daher die entsprechende Summe durchführen, die die Summe von O (n) ergibt. Beachten Sie jedoch, dass die übliche Vorgehensweise darin besteht, das _Produkt_ der Komplexität jeder Schleife (also nicht die _max_) zu nehmen, aber dies führt hier zu einer zu lockeren Grenze, da die Anzahl der Iterationen der innersten Schleife in Abhängigkeit vom aktuellen Wert von variiert _ich_. – qwertyman

Interessant. Vielen Dank. – user6142489

Algorithmus Zeit Komplexität: i/= 2 in Schleifen

Antwort

Verwandte Themen