Was ist das Big-O einer verschachtelten Schleife, in der Anzahl von Iterationen in der inneren Schleife von der aktuellen Iteration der äußeren Schleife bestimmt wird?

Question

Was ist die Big-O Zeitkomplexität der folgenden verschachtelten Schleifen:

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

Wäre es O (N ^ 2) noch?

Answer 1

Ja, es ist immer noch O (n ^ 2), es hat einen kleineren konstanten Faktor, aber die O-Notation nicht beeinflussen.

Answer 2

Ja. Denken Sie an die Definition von Big-O: O (f (n)) definitions sagt, dass die Laufzeit T (n) ≤ kf (n) für eine konstante k . In diesem Fall wird die Anzahl der Schritte sein (n-1) + (n-2) + ... + 0 , die auf die Summe von 0 bis n-1 umlagert; dies ist

T (n) = (n-1) ((n-1) + 1) / 2 .

Neu anordnen, dass und Sie können sehen, dass T (n) immer ≤ 1/2 (n²) sein; durch die Definition, also T (n) = O (n²) .

Answer 3

Es ist N im Quadrat, wenn Sie die System.out.printin ignorieren. Wenn Sie davon ausgehen, dass die durch die Zeit genommen, wird in seinem Ausgang linear sein (was sie kann auch nicht sein, natürlich), ich vermute, dass Sie mit O am Ende ((N ^ 2) * log N).

Ich erwähne dies nicht wählerisch zu sein, sondern nur darauf hinweisen, dass Sie nicht nur die offensichtlichen Schleifen berücksichtigen müssen, wenn die Komplexität der Arbeit aus -. Sie an der Komplexität suchen müssen, was man auch ohne weiteres als

Answer 4

Ja, wäre es N zum Quadrat. Die tatsächliche Anzahl der Schritte würde die Summe von 1 bis N, die 0,5 * (N - 1) ^ 2, wenn ich mich nicht irrt. Big O berücksichtigt nur den höchsten exponant und keine Konstanten, und somit ist dies immer noch N zum Quadrat.

Answer 5

Wenn Sie haben N = 10, Sie Iterationen wären: 9 + 10 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (Dies ist. Zehn Iterationen und neun Iterationen plus acht Iterationen ... usw.).

Nun müssen Sie in die Zugabe zu finden, wie oft Sie eine N (10 im Beispiel) bekommen:

1: (10) 2: (9 + 1), 3: (8 + 2), 4: (7 + 3), 5: (6 + 4). Die 5-mal ist ... und liegt 5 Iterationen.

Jetzt wissen Sie, dass Sie fünf Zehner + 5 haben:

10 (5) + 5

In Bezug auf f (n) (oder N), können wir leicht sehen, dass dies wäre:

f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 ... das ist genau die Komplexität dieser verschachtelte Schleife.

Aber das asymptotische Verhalten von Big O bedenken, können wir loswerden die weniger signifikanten Werte von f (n), die die einzelnen n und die Nenner sind.

Ergebnis: O (n ^ 2)

Answer 6

AFAIL, von der inneren Schleife durch Äußeren ist für die Berechnung der verschachtelten Schleife Komplexität angemessene Weise begonnen werden.