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

23

$T(n) = T(n-1) + T(n-2) + \Theta(1)$ $T(n) = \Theta(\phi^n)$ $\phi$ $\phi = \frac{(1 + \sqrt{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

Ω

$\Omega$

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)= \Omega(c^{n})$

— wabbit
źródło