Laufzeitenanalyse von Programmfragment

InformaticNewB

Hallo liebe Community,

ich bin neu im Informatikbereich und stoße gerade auf die Laufzeitanalyse.
Es ist eine Schleife gegeben, zu der wir eine Laufzeitanalyse mittels Vollständiger Induktion angeben sollen.
Mein Problem ist nun, dass ich überhaupt nicht weis wie ich anfangen soll.

Hier mal die Schleife:

int summe = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 2^i; j++) {
summe += 1;
}
}

Was da passiert verstehe ich soweit. Wir sollten im Voraus eine Vermutung abgeben, in welcher Laufzeitklasse dieses Programmfragment liegt.
Natürlich habe ich mich hinsichtlich der O-Notation schlau gemacht und vermute, dass es in der Laufzeitklasse O(n²) liegt.

Ich hab nur leider einfach keinen Schimmer, wie ich nun meine Vermutung mittels Vollständiger Induktion belegen kann.
Vielleicht kann mir ja einer von euch den richtigen Weg weisen.
Vielen Dank im Voraus für eure Aufmerksamkeit!
LG

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.

Laufzeitenanalyse von Programmfragment

Jetzt mitmachen!

Tags