wake-up-neo.com

Zeitkomplexität der verschachtelten for-Schleife

Ich muss die zeitliche Komplexität des folgenden Codes berechnen:

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

Ist es O (n ^ 2) ?

19
yyy

Ja, verschachtelte Schleifen sind eine Möglichkeit, schnell eine große O-Notation zu erhalten.

Normalerweise (aber nicht immer) führt eine in einer anderen verschachtelte Schleife zu O (n²).

Denken Sie darüber nach, die innere Schleife wird i-mal ausgeführt, für jeden Wert von i. Die äußere Schleife wird n-mal ausgeführt.

so sehen Sie ein Ausführungsmuster wie folgt: 1 + 2 + 3 + 4 + ... + n-mal 

Daher können wir die Anzahl der Codeausführungen beschränken, indem wir sagen, dass sie offensichtlich mehr als n-mal ausgeführt werden (untere Schranke), aber wie oft werden wir den Code ausführen?

Nun, mathematisch können wir sagen, dass es nicht mehr als n²-mal ausgeführt wird, was ein Worst-Case-Szenario und damit unsere Big-Oh-Grenze von O (n²) ergibt. (Für weitere Informationen, wie wir dies mathematisch sagen können, schauen Sie sich die Power Series an.)

Big-Oh misst nicht immer genau, wie viel Arbeit geleistet wird, sondern liefert in der Regel eine zuverlässige Annäherung an den Worst-Case-Fall.


4 Jahre später Edit: Weil dieser Beitrag anscheinend ziemlich viel Verkehr bekommt. Ich möchte ausführlicher erklären, wie wir die Ausführung mithilfe der Leistungsreihe an O (n²) gebunden haben

Von der Website: 1 + 2 + 3 + 4 ... + n = (n² + n)/2 = n²/2 + n/2. Wie machen wir das dann zu O (n²)? Was wir (im Grunde) sagen, ist, dass n²> = n²/2 + n/2. Ist das wahr? Lass uns eine einfache Algebra machen.

  • Multipliziere beide Seiten mit 2, um zu erhalten: 2n²> = n² + n? 
  • Erweitern Sie 2n², um zu erhalten: n² + n²> = n² + n?
  • N² von beiden Seiten abziehen, um zu erhalten: n²> = n?

Es sollte klar sein, dass n²> = n ist (nicht streng größer als in dem Fall, in dem n = 0 oder 1 ist), vorausgesetzt, dass n immer eine ganze Zahl ist.

Die tatsächliche Komplexität von Big O unterscheidet sich geringfügig von dem, was ich gerade gesagt habe, aber dies ist das Wesentliche. Tatsächlich fragt die Komplexität von Big O, ob es eine Konstante gibt, die wir für eine Funktion anwenden können, die größer als die andere ist, für ausreichend große Eingabe (siehe wikipedia page).

42
AndyG

Dies lässt sich schnell erklären, indem Sie es visualisieren.

wenn sowohl i als auch j von 0 bis N sind, kann man leicht O (N ^ 2) erkennen.

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

in diesem Fall ist es:

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O

Dies ergibt 1/2 von N ^ 2, was immer noch O (N ^ 2) ist.

21
Krys Jurgowski

In der Tat ist es O (n ^ 2). Siehe auch ein sehr ähnliches Beispiel mit derselben Laufzeit hier .

9
Chris Bunch

Zunächst werden Schleifen betrachtet, bei denen die Anzahl der Iterationen der inneren Schleife unabhängig vom Wert des Index der äußeren Schleife ist. Zum Beispiel:

 for (i = 0; i < N; i++) {
     for (j = 0; j < M; j++) {
         sequence of statements
      }
  }

Die äußere Schleife wird N-mal ausgeführt. Bei jeder Ausführung der äußeren Schleife führt die innere Schleife M-mal aus. Folglich führen die Anweisungen in der inneren Schleife insgesamt N · M-mal aus. Somit ist die Gesamtkomplexität für die beiden Schleifen O (N2).

1
napender

Bei der ersten Iteration der äußeren Schleife (i = 1) wird die innere Schleife 1-mal Wiederholt. Bei der zweiten Iteration der äußeren Schleife (i = 2) wird die innere Schleife 2-mal wiederholt Bei der 3. Iteration der äußeren Schleife (i = 3) wird die innere Schleife 3-mal wiederholt
.
.
Bei der FINAL-Iteration der äußeren Schleife (i = n) wird die innere Schleife N-mal durchlaufen

Die Gesamtanzahl der Anweisungen in der inneren Schleife Ist also gleich der Summe der ganzen Zahlen von 1 bis n.

((n)*n) / 2 = (n^2)/2 = O(n^2) times 
0
user2831683