Beiträge von Chri86

Chri86

Hallo!

Ich mir das Beispiel mal kurz angesehen und eine Formel für die Laufzeit abgeleitet.

Achten wir zuerst einmal darauf wie oft die innerste Schleife ausgeführt wird in Abhängigkeit zur Eingabegröße n.
φ(i) bezeichnet hier die Anzahl der Ausfühurngen der inneren Schleife wenn n den Wert i annimmt.

Code

φ(0) = 2                     -- Das hier sollte klar sein, da (int j = 0; j <= 2^i; j++) -> j <= 1 = sind 2 Durchläufe
φ(1) = φ(0) + 2[SUP]1 [/SUP]+ 1         -- wegen j <= 2[SUP]1[/SUP] folgen 3 durchläufe + alle vorherigen durchläufe (φ(0))

Die Anazhl der Ausführungen können wir daher als rekursive Formel definieren:

Code

φ(i) = φ(i-1) + 2[SUP]i[/SUP] + 1

Schauen wir uns jetzt mal an wie oft die innerste Schleife ausgeführt wird:

Code

φ(0) = 2
φ(1) = 2 + 3 =                        5
φ(2) = 2 + 3 + 5 =                    10
φ(3) = 2 + 3 + 5 + 9 =                19
φ(4) = 2 + 3 + 5 + 9 + 17 =           36
usw.

Das ganze können wir auch mittels Summenformel darstellen und anschließend vereinfachen:

Code

SUM(0,n) (2[SUP]i[/SUP] + 1)
= SUM(0,n) (2[SUP]i[/SUP]) + n + 1          //SUM(0,n) 1 = n + 1
= SUM(1,n) (2[SUP]i[/SUP]) + 1 + n + 1    //Summe von 1 starten lassen und ersten summanden 2[SUP]0[/SUP] = 1 addieren
= 2*(2[SUP]n[/SUP]-1) + n + 2                //SUM(1,n) (2[SUP]i[/SUP]) = 2*(2[SUP]n[/SUP]-1)  ist die Summenformel für die Summe der ersten n 2er Potenzen

Unsere Vermutung ist also dass wir die Laufzeit wie folgt berechnen können:

Code

ψ(i) = 2*(2[SUP]i[/SUP]-1) + i + 2

Nun müssen wir beweisen dass diese Vermutung auch stimmt.

Beim Beweis durch Induktion beginnt man zuerst mit dem Basisfall, hier ist das n = 0:

Code

φ(0) = 2
ψ(0) = 2*(2[SUP]0[/SUP]-1) + 0 + 2 = 2

Das stimmt soweit mal, nun gehen wir davon aus dass ψ(i) korrekt ist, und zeigen dass auch ψ(i+1) stimmt:

Code

φ(i+1) = φ(i) + 2[SUP](i+1)[/SUP] + 1


Einsetzen unserer Formel für φ(i) ergibt:


 = 2*(2[SUP]i[/SUP] - 1) + i + 2 + 2[SUP](i+1)[/SUP] + 1
 = 2[SUP](i+1)[/SUP] - 2 + i + 2 + 2[SUP](i+1)[/SUP] + 1
 = 2[SUP](i+1)[/SUP] + 2[SUP](i+1)[/SUP] + i + 1
 = 2*(2[SUP](i+1)[/SUP] - 1) + (i + 1) + 2
 = ψ(i+1)

Alles anzeigen

Das Ergebnis entspricht genau der Definition von ψ(i+1), also stimmt unsere Vermutung.

Die Laufzeit ist also nicht O(n²) sondern O(2*(2ⁿ-1) + n + 2) was wir zu O(2ⁿ) kürzen können.

Ich hoffe, dass ich hier keinen Fehler gemacht habe und gebe natürlich keine Garantie dafür dass das die gewünschte Lösung ist. Aber dass die Laufzeit in O(2ⁿ) ist kannst du dir veranschaulichen indem du die Anazhl der Durchläufe der inneren Schleife beim allerletzten Schleifendruchlauf der äußeren Schleife ansiehst, was gleich 2ⁱ ist, wobei i = n ist.