Złożoność rekurencyjnego algorytmu Fibonacciego

13

Korzystanie z następującego rekurencyjnego algorytmu Fibonacciego:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

Jeśli wprowadzę cyfrę 5, aby znaleźć Fib (5), wiem, że to da wynik 5, ale jak zbadać złożoność tego algorytmu? Jak obliczyć wymagane kroki?

algorithms time-complexity recursion żartowniś
źródło
1
cs.berkeley.edu/~vazirani/algorithms/chap0.pdf
avi
Szukałem tego samego i natknąłem się na ten film MyCodeSchool. Polecam to sprawdzić.
snbk97

Odpowiedzi:

23

T(n)=T(n−1)+T(n−2)+Θ(1)T(n)=Θ(ϕn)ϕϕ=(1+5)2

Jeśli chcesz dowiedzieć się więcej na temat rozwiązywania nawrotów, zdecydowanie zalecamy przeczytanie rozdziału 4 wstępu do algorytmów .

ees_cu
źródło
0

jako alternatywa dla relacji powtarzalności / analizy matematycznej (ale nie substytut ) prostym ćwiczeniem empirycznym, najwyraźniej nie uczonym zbyt często na zajęciach, ale bardzo pouczającym, jest policzenie liczby wykonań funkcji, a następnie wykres liczby dla zakresu małych n danych wejściowych, a następnie krzywa dopasowuje wynik. wyniki będą zasadniczo ściśle odpowiadać teoretycznemu podejściu matematycznemu.

dobry materiał pomocniczy do tego ćwiczenia można znaleźć w bezpłatnym internetowym rozdziale 3, czas działania algorytmów / Podstawy informatyki , Ullman

vzn
źródło
1) Rysowanie w żaden sposób nie zastępuje analizy formalnej. Łatwo go oszukać. 2) Myślę, że podajesz w błąd źródło, które zacytowałeś. Wspominają o spiskowaniu, ale nie jako sposób na określenie „złożoności”. 3) FWIW, nie zgadzam się z tym podejściem i jest ono używane tak, jak przedstawia to Ullman, ale to nie twoja wina.
Raphael
1
odpowiedź zaczyna się od twojego wyłączenia odpowiedzialności, mówiąc, że spisek nie zastępuje analizy matematycznej . kreślenie jest metodą naukową, a stwierdzenie, że czasem jest oszukiwane, polega na poznaniu / wywołaniu statystycznych aspektów danych, co jest kolejnym najważniejszym aspektem analizy naukowej . myśleć, że można go „łatwo oszukać” jest dość dramatyczny, zdarzają się przypadki „patologiczne”, w których zawodzi, ale zazwyczaj są one „wymyślone” ... chodziło o zbadanie złożoności algorytmu, a analiza empiryczna jest kluczowym aspektem / kąt na to, i oczywiście nie jedyny kąt itp ...
vzn
0

Wynik Fib (n) jest sumą wszystkich wywołań rekurencyjnych, które zwróciły 1. Dlatego istnieją dokładnie rekurencyjne wywołania Fib (n) oceniające Fib (1). Zatem czas wykonania wynosi Ω (fib (n)); musisz pokazać, że połączenia zwracające 0 i inne połączenia rekurencyjne nie dodają się do tego znacząco.

To samo rozumowanie dotyczyłoby każdej funkcji rekurencyjnie zdefiniowanej, która zwraca 1, 0 lub wynik innego wywołania rekurencyjnego.

gnasher729
źródło
Ω
Edytuj odpowiedź, jeśli masz do niej mocne zdanie.
gnasher729,
0

T(n)=T(n−1)+T(n−2) T(n)>2T(n−2)T(n−1)>T(n−2)T(n)=Ω(cn)

wabbit
źródło