Złożoność obliczeniowa sekwencji Fibonacciego

Rozumiem notację Big-O, ale nie wiem, jak ją obliczyć dla wielu funkcji. W szczególności starałem się zrozumieć złożoność obliczeniową naiwnej wersji sekwencji Fibonacciego:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Jaka jest złożoność obliczeniowa sekwencji Fibonacciego i jak jest obliczana?

Modelujesz funkcję czasu do obliczenia Fib(n)jako sumę czasu do obliczenia Fib(n-1)plus czas do obliczenia Fib(n-2)plus czas do ich dodania ( O(1)). Fib(n)Zakłada się, że powtórne oceny tego samego zajmują ten sam czas - tzn. Nie stosuje się zapamiętywania.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Rozwiązujesz tę relację powtarzalności (na przykład używając funkcji generujących) i otrzymujesz odpowiedź.

Alternatywnie możesz narysować drzewo rekurencji, które będzie miało głębokość ni intuicyjnie zorientuje się, że ta funkcja jest asymptotycznie . Następnie możesz udowodnić swoje przypuszczenie poprzez indukcję.O(2n)

Baza: n = 1jest oczywista

Zakładamy , dlategoT(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1) co jest równe

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

Jednak, jak zauważono w komentarzu, nie jest to ścisłe ograniczenie. Ciekawym faktem na temat tej funkcji jest to, że T (n) jest asymptotycznie taka sama jak wartość, Fib(n)ponieważ oba są zdefiniowane jako

f(n) = f(n-1) + f(n-2).

Liście drzewa rekurencyjnego zawsze zwracają 1. Wartość Fib(n)jest sumą wszystkich wartości zwróconych przez liście w drzewie rekurencyjnym, która jest równa liczbie liści. Ponieważ każdy liść potrzebuje O (1) do obliczenia, T(n)jest równy Fib(n) x O(1). W związku z tym ścisłym związkiem tej funkcji jest sama sekwencja Fibonacciego (~ ). Możesz dowiedzieć się o tej ścisłej więzi, korzystając z funkcji generowania, o których wspomniałem powyżej.θ(1.6n)

Wystarczy zadać sobie pytanie, ile instrukcji należy wykonać, aby F(n)je wypełnić.

Na F(1)odpowiedź jest 1(pierwsza część warunkowa).

Ponieważ F(n)odpowiedź brzmi F(n-1) + F(n-2).

Jaka funkcja spełnia te zasady? Wypróbuj ⁿ (a> 1):

a ⁿ == a ^(n-1) + a ^(n-2)

Podziel przez ^(n-2) :

a ² == a + 1

Rozwiąż ai otrzymasz (1+sqrt(5))/2 = 1.6180339887, inaczej zwany złotym współczynnikiem .

Zajmuje to zatem czas wykładniczy.

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)

W MIT jest bardzo miła dyskusja na temat tego konkretnego problemu . Na stronie 5 podkreślają, że jeśli założymy, że suma zajmuje jedną jednostkę obliczeniową, czas wymagany do obliczenia Fib (N) jest bardzo ściśle związany z wynikiem Fib (N).

W rezultacie możesz przejść bezpośrednio do bardzo zbliżonego przybliżenia serii Fibonacciego:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

i powiedzmy zatem, że najgorszym przypadkiem naiwnego algorytmu jest

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: Dyskusja na temat wyrażenia w formie zamkniętej liczby N-tego Fibonacciego na Wikipedii, jeśli chcesz uzyskać więcej informacji.

Możesz go rozwinąć i mieć wizualizację

     T(n) = T(n-1) + T(n-2) <
     T(n-1) + T(n-1) 

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

Jest on ograniczony na dolnym końcu 2^(n/2)i na górnym końcu przez 2 ^ n (jak zauważono w innych komentarzach). Ciekawym faktem tej rekurencyjnej implementacji jest to, że ma ona ścisłą asymptotyczną granicę samego Fib (n). Fakty te można streścić:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

Jeśli chcesz, ciasne ograniczenie można jeszcze bardziej zmniejszyć za pomocą zamkniętej formy .

Odpowiedzi na dowody są dobre, ale zawsze muszę wykonać kilka iteracji ręcznie, aby naprawdę się przekonać. Narysowałem więc małe drzewo wywołujące na mojej tablicy i zacząłem liczyć węzły. Dzielę swoje liczby na wszystkie węzły, węzły liści i węzły wewnętrzne. Oto co mam:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

To, co natychmiast się wyskakuje, to liczba węzłów liści fib(n). Zauważyłem jeszcze kilka iteracji, że liczba wewnętrznych węzłów jest fib(n) - 1. Dlatego całkowita liczba węzłów wynosi 2 * fib(n) - 1.

Ponieważ upuść współczynniki przy klasyfikacji złożoności obliczeniowej, ostateczna odpowiedź θ(fib(n)).

Złożoność czasową algorytmu rekurencyjnego można lepiej oszacować przez narysowanie drzewa rekurencyjnego. W tym przypadku relacja powtarzalności dla narysowanego drzewa rekurencyjnego wynosiłaby T (n) = T (n-1) + T (n-2) + O (1) zauważ, że każdy krok wymaga O (1), co oznacza stały czas, ponieważ wykonuje tylko jedno porównanie, aby sprawdzić wartość nw bloku, jeśli drzewo rekurencji wyglądałoby jak

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Powiedzmy tutaj, że każdy poziom powyższego drzewa jest oznaczony przez:

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

powiedzmy, że przy określonej wartości i drzewo kończy się, taki przypadek miałby miejsce, gdy ni = 1, stąd i = n-1, co oznacza, że ​​wysokość drzewa wynosi n-1. Zobaczmy teraz, ile pracy wykonano dla każdej z n warstw w drzewie. Zauważ, że każdy krok zajmuje czas O (1), jak podano w relacji powtarzalności.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

ponieważ i = n-1 to wysokość pracy drzewa wykonanej na każdym poziomie będzie

i work
1 2^1
2 2^2
3 2^3..so on

Stąd suma wykonanej pracy będzie sumą pracy wykonanej na każdym poziomie, stąd będzie to 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1), ponieważ i = n-1. Według szeregów geometrycznych suma ta wynosi 2 ^ n, stąd całkowita złożoność czasu wynosi O (2 ^ n)

Według mnie jest O(2^n)tak, ponieważ w tej funkcji tylko rekurencja zajmuje dużo czasu (dziel i zwyciężaj). Widzimy, że powyższa funkcja będzie kontynuowana w drzewie, dopóki liście nie zbliżą się, gdy osiągniemy poziom F(n-(n-1))tj F(1). Tak więc tutaj, gdy zanotujemy złożoność czasową występującą na każdej głębokości drzewa, seria podsumowań jest następująca:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

to jest kolejność 2^n [ O(2^n) ].

Naiwna rekurencyjna wersja Fibonacciego jest z założenia wykładnicza ze względu na powtarzalność w obliczeniach:

W katalogu głównym obliczasz:

F (n) zależy od F (n-1) i F (n-2)

F (n-1) ponownie zależy od F (n-2) i F (n-3)

F (n-2) ponownie zależy od F (n-3) i F (n-4)

wtedy na każdym poziomie są 2 wywołania rekurencyjne, które marnują dużo danych w obliczeniach, funkcja czasu będzie wyglądać następująco:

T (n) = T (n-1) + T (n-2) + C, ze stałą C.

T (n-1) = T (n-2) + T (n-3)> T (n-2) następnie

T (n)> 2 * T (n-2)

...

T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))

Jest to tylko dolna granica, która do celów analizy powinna wystarczyć, ale funkcja czasu rzeczywistego jest współczynnikiem stałej według tej samej formuły Fibonacciego, a forma zamknięta jest znana jako wykładniczy złoty współczynnik.

Ponadto można znaleźć zoptymalizowane wersje Fibonacciego za pomocą programowania dynamicznego, takiego jak to:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

Jest to zoptymalizowane i wykonuje tylko n kroków, ale ma również charakter wykładniczy.

Funkcje kosztów są definiowane od wielkości wejściowej do liczby kroków w celu rozwiązania problemu. Gdy zobaczysz dynamiczną wersję Fibonacciego ( n kroków do obliczenia tabeli) lub najłatwiejszy algorytm do ustalenia, czy liczba jest liczbą pierwszą ( sqrt (n) do analizy poprawnych dzielników liczby). możesz myśleć, że te algorytmy to O (n) lub O (sqrt (n)), ale to po prostu nieprawda z następującego powodu: Dane wejściowe do Twojego algorytmu to liczba: n , używając notacji binarnej wielkość wejściowa dla liczba całkowita n to log2 (n), a następnie zmiana zmiennej

m = log2(n) // your real input size

poznajmy liczbę kroków w zależności od wielkości wejściowej

m = log2(n)
2^m = 2^log2(n) = n

koszt algorytmu w zależności od wielkości wejściowej wynosi:

T(m) = n steps = 2^m steps

i dlatego koszt jest wykładniczy.

Można to łatwo obliczyć za pomocą wywoływania funkcji diagramu. Po prostu dodaj wywołania funkcji dla każdej wartości n i sprawdź, jak rośnie liczba.

Big O oznacza O (Z ^ n), gdzie Z jest złotym stosunkiem lub około 1,62.

Zarówno liczby Leonardo, jak i liczby Fibonacciego zbliżają się do tego współczynnika, gdy zwiększamy n.

W przeciwieństwie do innych pytań Big O, zmienność danych wejściowych nie jest zmienna, a zarówno algorytm, jak i implementacja algorytmu są jasno określone.

Nie ma potrzeby stosowania złożonej matematyki. Po prostu wykreśl poniższe wywołania funkcji i dopasuj funkcję do liczb.

Lub jeśli znasz złoty podział, rozpoznasz go jako taki.

Ta odpowiedź jest bardziej poprawna niż odpowiedź zaakceptowana, która twierdzi, że zbliży się do f (n) = 2 ^ n. Nigdy nie będzie. Zbliża się do f (n) = golden_ratio ^ n.

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

http://www.ics.uci.edu/~eppstein/161/960109.html

czas (n) = 3F (n) - 2