Złozoność obliczeniowa kodu rekurencyjnego

Cześć wszystkim.

Głowie się z zadaniem o tematyce powyżej. O ile z prostymi kodami jakoś tam sobie radze, tak z tymi bardziej złożonymi nie moge sobie dać rady.
Kod :

FIBONACCI(n)

1. if n<=1

2.    then return n
   

3.    else return FIBONACCI(n-1) + FIBONACCI(n-2)
   

Polecenie, jako analiza algorytmu wyznaczającego liczby Fibonacciego. Szczerze mówiąc, nie mam pojęcia co tu się dzieje. Kod wydaje się banalnie prosty, a nie wiem nawet jak sie za niego zabrać.
Nie chcę gotowego rozwiązania. Proszę tylko o jakieś cenne wskazówki, które pomogą mi poradzić sobie z tym i podobnymi zadaniami.

Pozdrawiam

Proste (ale mało uniwersalne) rozumowanie. Rekurencję trzeba stosować tak długo, aż argumentami funkcji FIBONACCI staną się jedynki => FIBONACCI(n) będzie liczony przez sumowanie jedynek => złożoność algorytmu = f_n. Z wzoru Bineta http://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego#Wz.C3.B3r_Bineta wynika, że złożoność jest wykładnicza.

Moim problemem jest to, że brak u mnie myśli abstrakcyjnej.
Doszedłem do wniosku, ze funkcją wyrażającą ilosc danych, bedzie po prostu 1/(1-x-x^2), prosto z wikipedii, biorąc pod uwage, że w pseudokodzie nie ma nic ponad samo obliczanie kolejnej liczby Fibonacciego, czyli po prostu standard.
n<1 bedzie zależało od tego czy funkcja jest optymistyczna, średnia czy pesymistyczna, tak? Czy się mylę.

Mylisz się, złożoność jest wykładnicza (dowód w poprzednim poście). W tym problemie nie ma sensu rozróżnianie złożoności optymistycznej, pesymistycznej i średniej.

Lukiskradacz napisał(a):

Cześć wszystkim.

Kod :

FIBONACCI(n)

1. if n<=1

2.    then return n
   

3.    else return FIBONACCI(n-1) + FIBONACCI(n-2)
   

To jest bardzo nieefektywny algorytm. Inne, wielokrotnie szybsze rozwiązanie jest takie (dam w pythonie np, nie wiem czy go znasz):

def fibbonacci(n):
    a = 0
    b = 1
    for i in range(n):
        b += a
        a = b-a
    return a

I zobacz co tu się dzieje. Tu najprościej jest przeanalizować co się dzieje z a i b w każdym kroku pętli. Rekurencja wydaje się być prosta ale tylko z pozoru.

@drorat1, dlaczego taki rozwlekły kod?;)

def fibbonacci(n):
    a,b = 0,1
    for i in range(n):
       a,b = b,a+b
    return a

Ah tak, masz racje. Wykazałem sie głupotą, w końcu wzór który podałem wraz z kolejnymi wyrażeniami zmniejsza swoja wartosc a nie zwiększa.. wybaczcie, cięzki dzień.

Co do fragmentu kodu, jest on oczywiscie narzucony odgórnie.
Programuje w Javie. O ile można to już nazwac programowaniem.

Co do samego tematu dalej, zasugeruje sie faktem, ze jest to f wykładnicza i spróbuje skręcić jakiś wzór.
Jestem wdzięczny za zainteresowanie tematem. Musze czym predzej poszerzyć moją wiedze teoretyczną która jak widać, jest na poziomie marnym :) Pisanie kodu idzie mi jednak znacznie lepiej.

Napisałem program (w Javie) porównujący efektywność kilku najprostszych algorytmów liczenia wyrazów ciągu Fibonacciego:

• post @drorat1'a, zmienne typu double
• post @drorat1'a, zmienne typu BigInteger
• wzór Bineta, zmienne typu double
• wzór Bineta, zmienne typu BigDecimal.
  Zwyciężył (z minimalną przewagą nad pierwszym) algorytm trzeci. Niestety oba te algorytmy dość szybko dają błędne wyniki. Typowe czasy wykonania (w milisekundach):
  
  

Przeglądałem właśnie to co jest w Wiki:
http://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego

Tam niżej jest ten wzór Eulera-Bitneta, jak również i przybliżony wzór. Na floatach mogą być po prostu błędy, tylko zastanawiam się na ile znaczące w praktyce. Co do rekurencji, to się może nadaje do liczenia elementów może do 10-tego, w pythonie liczenie takiego 50 elementu działa na tyle koszmarnie wolno, że jest to po prostu jakiś nonsens.

Dałem tu przykład z tym a i b w pętli ponieważ nie potrafię zrozumieć jak można w ogóle zawracać sobie głowę jakimiś tam nieoptymalnymi rozwiązaniami które tak naprawdę ujawniają się jak się bierze pod uwagę języki z dynamicznym typowaniem danych. Podobnie można by analizować np. sortowanie bąbelkowe vs inne bardziej wydajne algorytmy.

Na floatach mogą być po prostu błędy, tylko zastanawiam się na ile znaczące w praktyce.

Nie wiem jak duże liczby ciągu Fibonacciego są używane w praktyce. Liczba f₁₀₀ jest 21-cyfrowa, obliczona Twoim wzorem (ale na typie zmiennoprzecinkowym) ma 14 pierwszych cyfr poprawnych.

bogdans napisał(a):

Na floatach mogą być po prostu błędy, tylko zastanawiam się na ile znaczące w praktyce.

Nie wiem jak duże liczby ciągu Fibonacciego są używane w praktyce. Liczba f₁₀₀ jest 21-cyfrowa, obliczona Twoim wzorem (ale na typie zmiennoprzecinkowym) ma 14 pierwszych cyfr poprawnych.

Przecież te obliczenia wykonuje się nie na liczbach (i typach) rzeczywistych ale całkowitych. Więc jak wziąć tą pętle w której są dokonywane operacje na a i b o typie całkowitym to gdzie tu jest problem?

Mało domyślny jesteś, skoro piszę o typie zmiennoprzecinkowym, to znaczy że stosowałem inny język - bez automatycznego przechodzenia do "nieskończonego" typu całkowitego. Zatem liczyłem "na floatach".