Sind verschachtelte Schleifen immer O (n ^ k)?

Wenn ich eine Schleife in einer anderen Schleife habe, aber weiß, dass die innere Schleife nur einmal ausgeführt wird, ist dieser Algorithmus dann immer noch O (n ^ 2)?

For i = 1 to n do

     For j = 1 to i do

          If (i==j) do

              For k = 1 to n

                  {Do stuff}

Die sehr innere Schleife wird höchstens einmal ausgeführt, da isie nur jeinmal pro Iteration der zweiten Schleife gleich ist. Ist das noch n ^ 3?

algorithms John
quelle

Antworten:

Denk darüber so. Unabhängig von N wird die innerste Funktion immer nur einmal pro Ausführung der zweiten Schleife ausgeführt. Das heißt, die Häufigkeit, mit der es ausgeführt wird, hängt linear von N ab. Dies bedeutet, dass Sie alles innerhalb der ersten Schleife als lineare (O (n)) Zeitoperation behandeln können (vorausgesetzt, {do stuff} ist auch eine konstante Zeit). Wenn Sie die äußerste Schleife betrachten, sehen Sie, dass Sie etwas tun, das O (n) n-mal dauert. Dies bedeutet, dass die Gesamtlaufzeit O (n ^ 2) ist.

Wenn Sie N verdoppeln, gibt es insgesamt N ^ 2 zusätzliche Iterationen. Somit beträgt die Gesamtlaufzeit N ^ 2.

Oleksi
quelle

Vielen Dank! Das habe ich geglaubt, aber die Art und Weise, wie ich immer an verschachtelte Schleifen gedacht habe, hat mich verwirrt

John

@ John, kein Problem. Es ist schwierig, richtig zu machen. Es ist hilfreich, wenn Sie darüber nachdenken, N zu verdoppeln, und dann fragen, wie sich dies auf die Häufigkeit auswirkt, mit der Sie etwas tun.

Oleksi

Huh? Die erste und dritte Schleife hängen von n ab. Die Bedingung ist nur einmal pro Ausführung der zweiten Schleife wahr. Wir haben hier zwei n ^ 2 Aufgaben, das ij-Schleifenpaar und das ik-Schleifenpaar. Das Ergebnis ist jedoch immer noch n ^ 2.

Loren Pechtel

@ LorenPechtel whoops. Es tut uns leid. Ich habe das übersehen. Ich habe die Antwort aktualisiert, um dies widerzuspiegeln.

Oleksi

Nein, verschachtelte Schleifen bedeuten nicht automatisch, dass Ihr Algorithmus O (n ^ k) ist. Die grundlegende Arbeitseinheit in Ihrem Beispiel ist {Do stuff}, also müssen Sie zählen, wie oft dies als nErhöhung ausgeführt wird. Sie brauchen die jSchleife nicht einmal , da sie nur von 1 bis 1 zählt iund nichts tut, bis sie erreicht ist i. Nur bei dieser einen Iteration funktioniert es tatsächlich, daher lautet Ihr Beispielcode O (n ^ 2).

Bill die Eidechse
quelle