---

Geschrieben von deppensido am 25.04.2013 um 10:41:

  Laufzeit von Fibonacci-Algorithmus bestimmen

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

---

Geschrieben von Airblader am 27.04.2013 um 09:27:

 

Im naiven Ansatz ist die Laufzeit korrekt, ja.

---

Geschrieben von deppensido am 30.04.2013 um 14:08:

 

danke fürs nachschauen!

Grüße