Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Algorytm Fibonacciego - Złożoność obliczeniowa

aniap112 12 Lis 2016 22:34 840 0
  • #1 12 Lis 2016 22:34
    aniap112
    Poziom 1  

    Algorytm Fibonacciego - Złożoność obliczeniowa

    Mam za zadanie wyznaczyć złożoność postaci rekurencyjnej.
    wiem, że
    c1: wczytaj(n)
    c2: sprawdzenie czy $$ n< = 2 $$
    c3: wypisanie $$ f(n) = 1$$
    c4*2f(n)-1 : wywołanie funkcji $$f(n) = f(n-2)+f(n-1)$$
    c5: wypisanie $$f(n)$$

    wiem też, że liczba operacji dodawania jest równa F(n)-1
    i że złożoność ma być $$O(n)=( 2^n ) $$
    Bardzo proszę o wyjaśnienie.

    0 0