Laufzeit von Fibonacci-Algorithmus bestimmen |
| 25.04.2013, 10:41 | Auf diesen Beitrag antworten » |
| deppensido | 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 |
|
|
|
| 27.04.2013, 09:27 | Auf diesen Beitrag antworten » |
| Airblader | Im naiven Ansatz ist die Laufzeit korrekt, ja. |
| 30.04.2013, 14:08 | Auf diesen Beitrag antworten » |
| deppensido | danke fürs nachschauen! Grüße |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
