Informatiker Board | Algorithmen | Laufzeit von Fibonacci-Algorithmus bestimmen

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeit von Fibonacci-Algorithmus bestimmen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Laufzeit von Fibonacci-Algorithmus bestimmen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

Laufzeit von Fibonacci-Algorithmus bestimmen

Zitatantwort auf diesen Beitrag erstellen

Hallo,

ich versuche gerade für die rekursive Variante des Fibonacci-Algorithmus, also:

fib(n)
if n = 0 oder n = 1 return n
return fib(n-1) + fib(n-2)

die Laufzeit in Anzahl verwendeter Additionen zu bestimmen.

Meine Vermutung ist:

A(0) = 0
A(1) = 0 //da ja sofort n zurückgegeben wird und somit keine Additon statt findet

A(n) = A(n-1) + A(n-2) + 1 //für n >= 2 (da jeweils 2 Aufrufe statt finden und pro Aufruf jeweils maximal eine Additon statt findet)

stimmt das erst mal soweit. Wenn ich die Rekursionsgleichung auflöse müsste Laufzeit O( 2^n ) rauskommen. Wäre das auch korrekt?

Vielen Dank schon mal.

Grüße

Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von deppensido: 25.04.2013 11:34.

25.04.2013 10:41

Nehmen Sie deppensido in Ihre Freundesliste auf

Airblader Airblader ist männlich

Doppel-As

Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München

Im naiven Ansatz ist die Laufzeit korrekt, ja.

__________________
The best thing about a boolean is that even if you're wrong, you're only off by a bit.

27.04.2013 09:27

Nehmen Sie Airblader in Ihre Freundesliste auf

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

danke fürs nachschauen!

Grüße

30.04.2013 14:08

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeit von Fibonacci-Algorithmus bestimmen