Zgadzam się z pgaur i rickerbh, złożoność rekurencyjnego fibonacciego to O (2 ^ n).
Doszedłem do tego samego wniosku raczej uproszczeniem, ale nadal uważam, że jest to uzasadnione uzasadnienie.
Po pierwsze, chodzi o ustalenie, ile razy wywoływana jest funkcja rekurencyjna Fibonacciego (F () odtąd) podczas obliczania N-tej liczby Fibonacciego. Jeśli zostanie wywołany raz na numer w sekwencji od 0 do n, wówczas mamy O (n), jeśli zostanie wywołany n razy dla każdego numeru, otrzymamy O (n * n) lub O (n ^ 2), i tak dalej.
Tak więc, gdy F () jest wywoływana dla liczby n, liczba wywołań F () dla danej liczby od 0 do n-1 rośnie, gdy zbliżamy się do 0.
Na pierwszy rzut oka wydaje mi się, że jeśli ułożymy to wizualnie, narysowanie jednostki za każdym razem, gdy F () jest wywoływane dla danej liczby, mokro uzyskuje rodzaj piramidy (to znaczy, jeśli centrujemy jednostki poziomo ). Coś takiego:
n *
n-1 **
n-2 ****
...
2 ***********
1 ******************
0 ***************************
Pytanie brzmi: jak szybko powiększa się podstawa tej piramidy, gdy n rośnie?
Weźmy prawdziwy przypadek, na przykład F (6)
F(6) * <-- only once
F(5) * <-- only once too
F(4) **
F(3) ****
F(2) ********
F(1) **************** <-- 16
F(0) ******************************** <-- 32
Widzimy, że F (0) jest wywoływany 32 razy, czyli 2 ^ 5, co w tym przypadku próbki wynosi 2 ^ (n-1).
Teraz chcemy wiedzieć, ile razy F (x) jest wywoływane, i widzimy, ile razy F (0) jest wywoływane, jest tylko częścią tego.
Jeśli przenosimy mentalnie wszystkie * z linii F (6) do linii F (2) do linii F (1), widzimy, że linie F (1) i F (0) mają teraz równą długość. Co oznacza, że całkowite czasy F () są wywoływane, gdy n = 6 wynosi 2x32 = 64 = 2 ^ 6.
Teraz pod względem złożoności:
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)