Algorithm Complexity

ChillStudent

Hallo allerseits,

geg.:
sum = 0;
for (i = 0; i < n; i=i+2) {
for (j = 0; j < n * n; j++) {
sum++;
}
}

Meine Lösung = O(N³), könnte das so hinkommen? einmal das N^1 von der ersten Schleife und das N² ( n * n ) von der zweiten...N ^ 1 + N ^ 2 = N ^3?

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

SeppJ

Wenn die ganzen Additionen als konstant gelten, dann ist das N³, ja. Aber N¹ + N² != N³. Stattdessen N¹ + N² = N². Hier hast du jedoch N¹ * N² = N³.

ChillStudent

sry für den fehler, hab * gemeint

sum = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < i * i; j++) {
for (k = 0; k < j; k++) {
sum++;
}
}

hab hier noch ein problem...

erste schleife = N
zweite = N²
dritte = N(N+1)/2

liege ich da richtig mit 2*O(N³)=O(N³)? bin ein wenig verwirrt...

SeppJ

Deine Analyse der Einzelschleifen passt. Aber du rechnest wieder falsch zusammen. Dieses Mal stimmt zwar die Rechnung an sich (2*O(N³) ist wirklich O(N³)), aber du hast eben nicht 2*O(N³) = O(N³)+O(N³) vorliegen, sondern etwas anderes.

ChillStudent

könntest du mir en Tipp geben, wie ich das am besten rechnen kann?

otze

eine innere schleife geht immer multiplikativ in die Komplxität ein.

//edit ich würde als ansatz folgendes wählen:

for (i = 0; i < n; i++)
    for (j = 0; j < i * i; j++)
        for (k = 0; k < j; k++)
            sum++;

vereinfacht sich zu:

for (i = 0; i < n; i++)
    f(i)

Wenn wir die Komplexität von f kennen, können wir bestimmen, was die Gesamtlaufzeit ist. Also schauen wir uns f(i) an:

for (j = 0; j < i * i; j++)
        for (k = 0; k < j; k++)
            sum++;

vereinfacht sich zu

for (j = 0; j < i * i; j++)
        g(j)

und g(j) ist

for (k = 0; k < j; k++)
    sum++;

was offensichtlich O(j) ist.
das setzen wir in f(i) ein und sehen das j <= i^2. das heißt g(j) ist in O(i^2). Und die Schleife läuft von o bis i^2-1. Also f(i) ist O(i^2*i2)=O(i^4)
zuletzt wird f(i) n mal mit Argumenten 0...n aufgerufen und erhalten somit O(n^5)

ChillStudent

jetzt ist es doch verständlich, danke dir