Berechnungskomplexität der Fibonacci-Folge

Question

Ich verstehe die Big-O-Notation, aber ich weiß nicht, wie ich sie für viele Funktionen berechnen kann. Insbesondere habe ich versucht, die Berechnungskomplexität der naiven Version der Fibonacci-Folge herauszufinden:

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

Wie hoch ist die Komplexität der Fibonacci-Folge und wie wird sie berechnet?

Answer 1

Sie modellieren die Zeitfunktion zur Berechnung Fib(n) als Summe der zu berechnenden Zeit Fib(n-1) plus die Zeit für die Berechnung Fib(n-2) plus die Zeit, um sie zu addieren ( O(1) ). Dabei wird davon ausgegangen, dass wiederholte Auswertungen desselben Fib(n) nehmen die gleiche Zeit in Anspruch, d.h. es wird keine Memoisierung verwendet.

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

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

Lösen Sie diese Rekursionsbeziehung (z. B. mit Hilfe von erzeugenden Funktionen) und Sie erhalten die Antwort.

Alternativ können Sie auch den Rekursionsbaum zeichnen, der eine Tiefe von n und intuitiv herausfinden, dass diese Funktion asymptotisch ist O(2``n``) . Sie können dann Ihre Vermutung durch Induktion beweisen.

Basis: n = 1 ist offensichtlich

Angenommen, T(n-1) = O(2``n-1``) , daher

T(n) = T(n-1) + T(n-2) + O(1) was gleich ist mit

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

Wie jedoch in einem Kommentar angemerkt wurde, ist dies nicht die enge Grenze. Eine interessante Tatsache über diese Funktion ist, dass T(n) asymptotisch ist derselbe als den Wert von Fib(n) da beide definiert sind als

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

Die Blätter des Rekursionsbaums geben immer 1 zurück. Der Wert von Fib(n) ist die Summe aller von den Blättern des Rekursionsbaums zurückgegebenen Werte, die gleich der Anzahl der Blätter ist. Da jedes Blatt O(1) zur Berechnung benötigt, T(n) ist gleich Fib(n) x O(1) . Folglich ist die enge Grenze für diese Funktion die Fibonacci-Folge selbst (~ (1.6``n``) ). Sie können diese enge Schranke herausfinden, indem Sie, wie ich oben erwähnt habe, erzeugende Funktionen verwenden.

Answer 2

Fragen Sie sich einfach, wie viele Anweisungen ausgeführt werden müssen, um F(n) zu vervollständigen.

Für F(1) lautet die Antwort 1 (der erste Teil des Konditionals).

Für F(n) lautet die Antwort F(n-1) + F(n-2) .

Welche Funktion erfüllt also diese Regeln? Versuchen Sie eine n (a > 1):

a n \== a (n-1) + a (n-2)

Division durch a (n-2) :

a 2 \== a + 1

Lösen Sie für a und Sie erhalten (1+sqrt(5))/2 = 1.6180339887 , auch bekannt als die Goldener Schnitt .

Es dauert also exponentiell lange.

Answer 3

Ich stimme pgaur und rickerbh zu, die Komplexität von Rekursiv-Fibonacci ist O(2^n).

Ich bin mit einer ziemlich simplen, aber meiner Meinung nach immer noch gültigen Argumentation zu demselben Schluss gekommen.

Zunächst geht es darum, herauszufinden, wie oft die rekursive Fibonacci-Funktion (von nun an F()) bei der Berechnung der N-ten Fibonacci-Zahl aufgerufen wird. Wenn sie einmal pro Zahl in der Folge 0 bis n aufgerufen wird, dann haben wir O(n), wenn sie n-mal für jede Zahl aufgerufen wird, dann haben wir O(n*n) oder O(n^2), und so weiter.

Wenn also F() für eine Zahl n aufgerufen wird, nimmt die Anzahl der Aufrufe von F() für eine bestimmte Zahl zwischen 0 und n-1 zu, je mehr man sich 0 nähert.

Auf den ersten Blick scheint es mir, dass, wenn wir es visuell ausdrücken und jedes Mal, wenn F() für eine bestimmte Zahl aufgerufen wird, eine Einheit zeichnen, eine Art Pyramidenform entsteht (d.h. wenn wir die Einheiten horizontal zentrieren). Etwas wie dies:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

Die Frage ist nun, wie schnell sich die Basis dieser Pyramide vergrößert, wenn n wächst.

Nehmen wir einen realen Fall, zum Beispiel F(6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

Wir sehen, dass F(0) 32 Mal aufgerufen wird, was 2^5 entspricht, was für diesen Beispielfall 2^(n-1) ist.

Jetzt wollen wir wissen, wie oft F(x) überhaupt aufgerufen wird, und wir können sehen, dass die Anzahl der Aufrufe von F(0) nur ein Teil davon ist.

Wenn wir gedanklich alle * von den Zeilen F(6) bis F(2) in die Zeile F(1) verschieben, sehen wir, dass die Zeilen F(1) und F(0) jetzt gleich lang sind. Das bedeutet, dass F() insgesamt 2x32=64=2^6 aufgerufen wird, wenn n=6 ist.

Was nun die Komplexität betrifft:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

Answer 4

Es gibt eine sehr schöne Diskussion darüber spezifisches Problem am MIT . Auf Seite 5 wird darauf hingewiesen, dass die für die Berechnung von Fib(N) benötigte Zeit sehr eng mit dem Ergebnis von Fib(N) zusammenhängt, wenn man davon ausgeht, dass eine Addition eine Recheneinheit benötigt.

Daher können Sie direkt zur sehr engen Annäherung an die Fibonacci-Reihe übergehen:

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

und sagen daher, dass die Leistung des naiven Algorithmus im schlimmsten Fall

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

PS: Es gibt eine Diskussion über die geschlossener Ausdruck für die N-te Fibonacci-Zahl bei Wikipedia, wenn Sie weitere Informationen wünschen.

Answer 5

Sie können es erweitern und eine Visualisierung erhalten

     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)