[Lookbehind]

Ich bin zu dumm dazu glaub ich.

Ich würde gern etwas mehr in diese Richtung können. Wenn ich erstmal ne Formel da stehen habe, kann ich damit auch oft einigermaßen gut weiter rechnen. (Is dann ja größtenteils relativ simple Mathematik)
Aber wenn ich vom Quellcode auf diese Formel kommen soll, versagt es bei mir total. Ich komm auf alles Mögliche, aber nicht das, was die Musterlösung vorgibt.

Beispiel: Rekursive Fibonacci-Zahlen

#include <stdio.h>

int fibonacci(int n) {
	if(n==0) {
		return 0;
	} else {
		if(n==1) {
			return 1;
		} else {
			return (fibonacci(n-1) + fibonacci(n-2));
		}
	}
}

int main(int argc, char * argv[]) {
	int n=50;
	printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
	return 0;
}

Ja, ich weiß, es ist nicht besonders clever die Fibonacci-Zahlen rekursiv zu berechnen, weil das deutlich zu langsam ist. Es geht auch gar nicht darum einen effizienten Algorithmus zu finden, sondern das ich lernen möchte, die Laufzeit von sowas zu berechnen.

So weit ich das verstanden habe, wird die Funktion fibonacci durch den rekursiven Aufruf auf der untersten Ebene 2x aufgerufen, das ganze genau n/2 mal für jeden Zweig, als n/2*(2*c), da es 2 Zweige gibt 2*(n/2*(2*c)). Wenn man das nach oben durchspielt, gibt es diese Aufsplittung insgesamt n/2 mal. Damit komme ich dann letztlich auf n/2*(2*(n/2*(2*c))) (Die Klammern dienen in erster Linie der Übersicht). Wenn ich das aus multipliziere komme ich auf n^2*c, da man das c wohl vernachlässigen kann, bin ich also bei n^2.
Dass das nicht stimmt weiß ich wohl auch. Die Frage ist: Wie gehts richtig?
Kann mir bitte mal jemand erklären wie man an sowas ran geht, damit es auch funktioniert?

TIA

Look

[brokenclaw]

Hi.

Also, ich glaube in deiner Logik ist irgendwo ein Fehler drin. Zumindest kann ich nicht nachvollziehen wie du auf die n/2 kommst.

Ueberleg dir erstmal was passiert wenn du für n=0 einsetzt.
Dann wird nur
if(n==0) { return 0;
ausgeführt. Das ist konstant viel Arbeit. Die Laufzeit ist also für dieses Argument 1. Oder wenn T die Funktion sein soll, die deine Laufzeit angibt
T(0) = 1

Wenn du das selbe für n=1 machst kommst du ebenfalls auf eine konstante Laufzeit,
da die beiden ifs konstant viel Arbeit sind und in der Komplexitätsanalyse unter den Tisch fallen.
T(1) = 1

Für n=2 wird es jetzt das erste mal spannend. Da kommt man in den Nebenzweig mit dem rekursiven Aufruf ins Spiel also
return (fibonacci(n-1) + fibonacci(n-2));
was für unsere Laufzeit bedeutet dass
T(2) = T(2-1) + T(2-2) = T(1) + T(0)

Und das geht auch für allgemeine Zahlen so durch
T(n) = T(n-1) + T(n-2)

Um die Laufzeit von fibonacci(n) zu bestimmen musst du jetzt also folgende Rekursionsgleichung lösen
T(n) = T(n-1) + T(n-2)
mit den Anfangsbedingungen
T(0)=1
T(1)=1

Und das ist jetzt der Moment wo die `relativ simple` Mathematik ins Spiel kommt (:
sprich `erzeugende Funktionen` oder `charakteristische Polynome` oder einfach `Wolfram-Alpha`.
Ich sehe jetzt grad keinen naiven Weg das ganze zu lösen.

Es wäre für dich wahrscheinlich einfacher gewesen soetwas wie die Fakultät zu berechnen, da könnte man die resultierende Formel einfacher lösen. ^^

Ich hoffe ich konnte dir irgendwie weiterhelfen?

[Reckless]

Soweit ich mich erinnere, wird dort auch die Laufzeit berechnet:
http://www.youtube.com/watch?v=OQ5jsbhAv_M

Gruss

[ojas]

Und das geht auch für allgemeine Zahlen so durch
T(n) = T(n-1) + T(n-2)

Das ist schon mal ein guter Ansatz. Da T(i) > T(i-1) für alle i > 1 ist, folgt T(n) > T(n-2) + T(n-2) = 2T(n-2), was auf exponentielles Wachstum schließen lässt (das ja gerade dadurch gekennzeichnet ist, das eine Addition auf der Abszisse zu einer Multiplikation auf der Ordinate führt).

Aus gleichem Grund ist T(n) < T(n-1) + T(n-1) = 2T(n-1), was ebenfalls auf exponentielles Wachstum schließen lässt.

Die Laufzeit ist also nach oben und nach unten durch zwei exponentielle Funktionen beschränkt, muss also selbst exponentiell sein.

Allgemein heißt diese Art von Gleichung Rekursionsgleichung oder Differenzengleichung und du findest unter diesen Stichwörtern Verfahren, die explizite Form der Gleichung zu bestimmen.

[brokenclaw]

@ojas: Ahhhh... Stimmt. Eigentlich hätte man das wirklich mit scharfem hinsehen lösen können (:

[Lookbehind]

Erstmal herzlich willkommen im Forum brokenclaw

Danke für eure Erklärungen! Das hat mir, zumindest bei diesem einen Algorithmus schon mal weiter geholfen. Und auch bei den beiden anderen Implementierungen der Fibonacci-Zahl, die ich hier als Beispiel vorliegen hab, kam ich anschließend auf ein (wenigstens annähernd) richtiges Ergebnis.

Weiß jemand, wo ich weitere Übungen, mit Lösung, her bekomme? Respektive, wie ich überprüfen kann, ob meine Laufzeit-Berechnungen richtig waren?