Big O Summe der Ganzzahlen Laufzeit

Question

Ich habe versucht, Big O zu lernen und bin verwirrt auf einem Algorithmus, den ich gerade gestoßen bin. Der Algorithmus ist:

void pairs(int[] array){ 
    for (int i=0; i < array.length; i++){ 
    for (int j=i+1; j<array.length; j++){ 
     System.out.println(array[i]+","+array[j]); 
    } 
    } 
} 

Ich denke, die erste for-Schleife O(n) ist und ich weiß, die zweite for-Schleife O(1/2*n(n+1)) ist. Die Antwort auf das Problem war, dass die Laufzeit für die Funktion O(n^2) ist. Ich vereinfachte O(1/2*n(n+1)) zu O(1/2*(n^2+n)). So bin ich verwirrt, weil ich dachte, dass Sie die zwei Laufzeitbegriffe multiplizieren mussten, da die for-Schleife verschachtelt ist, die O(n) * O(1/2*(n^2+n)) geben würde. Ich vereinfachte dies auf O(1/2n^3 + 1/2n^2). Von dem, was ich von Big O verstehe, behältst du nur den größten Begriff, so würde dies auf O(n^3) reduzieren. Kann mir jemand helfen, wo ich falsch gelaufen bin? Nicht sicher, wie die Antwort ist O(n^2) anstelle von O(n^3).

Answer 1

Wenn Sie sagen, die innere Schleife ist O(1/2*n(n+1)), beschreiben Sie tatsächlich die große 0 Komplexität von beide Schleifen.

Um zu sagen, dass die äußere Schleife Komplexität hat, bedeutet O (N) grundsätzlich, dass ihr Körper N-mal läuft. Aber für die Berechnung der Komplexität der inneren Schleife haben Sie bereits alle Iterationen der äußeren Schleife berücksichtigt, weil Sie die Anzahl der Male addierten, die die innere Schleife über alle Iterationen der äußeren Schleife läuft. Wenn Sie erneut mit N multiplizieren, würden Sie sagen, dass die äußere Schleife selbst erneut N mal ausgeführt wird.

Anders ausgedrückt, was Ihre Analyse zeigt ist, dass die innere Schleife Körper (System.out.println Anruf) 1/2*n(n+1) insgesamt läuft. Das bedeutet, dass die Gesamtkomplexität der Zwei-Schleifen-Kombination O(1/2*n(n+1)) = O(n^2) ist. Die Gesamtkomplexität der Zwei-Schleifen-Kombination beschreibt, wie oft der innerste Code ausgeführt wird.

Answer 2

Ihr Fehler ist, die zweite Schleife als O(1/2n^2) Zählen ...
ersten, kann man deutlich sehen, es ist nach oben begrenzt auf N-1 (wenn j = 0)

erste Schleife klar N
zweite Schleife ist MAX ist von N-1 ...
threrefore, O (N^2) ...

wenn wir untersuchen es wenig mehr, wird zweite Schleife ausgeführt, wenn N-1i=0,
dann N-2 für i=1,
und ein einziges Mal für i=n-1,

dies 1/2n(n-1) = 1/2n^2 - 1/2n = O(n^2)
Hinweis dies auch alle Iteration der äußeren Schleife beinhaltet!