Zeitliche Komplexität einer dreifach verschachtelten Schleife

13

Bitte beachten Sie die folgende dreifach verschachtelte Schleife:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

Die Anweisung hier wird genau Mal ausgeführt. Könnte jemand erklären, wie diese Formel erhalten wurde? Vielen Dank.n(n+1)(n+2)6

algorithms time-complexity algorithm-analysis Xin
quelle
1
Die Frage Zeitkomplexitätsformel von verschachtelten Schleifen könnte ebenfalls von Interesse sein.
Juho

Antworten:

14

Sie können zählen, wie oft die innerste for-Schleife ausgeführt wird, indem Sie die Anzahl der Triplets (i,j,k) für die sie ausgeführt wird.

Durch die Schleifenbedingungen wissen wir, dass: 1≤i≤j≤k≤n . Wir können es auf das folgende einfache kombinatorische Problem reduzieren.

  • Stellen Sie sich n+2 rote Kästchen vor, die in einem Array von links nach rechts angeordnet sind.
  • Wähle 3 beliebige Kisten aus der n+2 Kisten und male sie blau an.
  • Bilden Sie ein Triplett (i,j,k) wie folgt:
    • = 1 + Anzahl roter Kästchen links vom ersten blauen Kästchen.i
    • = 1 + Anzahl der roten Kästchen links vom zweiten blauen Kästchen.j
    • = 1 + Anzahl der roten Kästchen links vom dritten blauen Kästchen.k

Wir müssen also nur die Anzahl der Auswahlmöglichkeiten für 3 Kästchen aus Kästchen zählen, also .n+2(n+23)

rizwanhudda
quelle
2
Gute Antwort! Die genauen Werte von i, j, k sind nicht wichtig. Wir müssen nur wissen, dass jede blaue Box in n möglichen Positionen platziert werden kann und dass ihre Positionen begrenzt sind: 2. kommt immer nach dem 1. und vor dem 3..
Dávid Natingga
@rizwanhudda Clear mit Ausnahme des Teils in n + 2 . Kannst du es bitte erklären? n + 3 sieht aus wie die richtige Zahl. +2n+2n+3
Saadtaame
1
@saadtaame Ja. Sie können sich vorstellen, rote Kästchen zu haben, aber Sie können 3 rote Kästchen zum Malen von Blau unter " n + 2 roten Kästchen" auswählen , da Sie das erste Kästchen nicht als blau färben können (Da i ≥ 1 )n+3n+2i≥1
rizwanhudda
3

Für mich ist es einfacher zu bemerken, dass die innere Schleife Mal ausgeführt wird und die Gesamtzahl der Ausführungen in der inneren Schleife istn−i

(n−i)+(n−i−1)+(n−i−2)+…+1

Dies kann wie folgt umgeschrieben werden und ausgeführt wird n - mal, so dass die Gesamtzahl der Ausführungen ist∑j=0n−in−i−jn

∑i=0n∑j=0n−in−i−j=n(n+1)(n+2)6
Andy Mcevoy
quelle
Eine Herausforderung für Sie: Stellen Sie sich vor, Sie haben eine x-verschachtelte Schleife. Entsprechend der vorherigen Antwort würde es ausführen (n + x-1) und x-mal wählen. Wie würden Sie Ihre Formel berechnen?
Dávid Natingga
Zum Glück hat der OP nicht nach x-nested gefragt! Wie erweitert sich die andere Antwort auf eine x-verschachtelte Schleife? Meine Antwort sollte nur mehr Summen von 0 nach n, 0 nach n-i_1, 0 nach n-i_2, ..., 0 nach n-i_x bringen. Aber ich würde nicht wissen, wie ich das berechnen soll.
Andy Mcevoy
1
Die Antwort wird für ein allgemeines x nicht explizit erweitert, aber der dargestellte Argumentationsprozess lässt sich leicht auf x-verschachtelte Schleifen übertragen. Sie fügen nur weitere blaue Kästchen hinzu. Ich weiß auch nicht, wie ich diese mehr Summen berechnen würde.
Dávid Natingga