wake-up-neo.com

Berechnungskomplexität der Fibonacci-Sequenz

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

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

Wie ist die rechnerische Komplexität der Fibonacci-Sequenz und wie wird sie berechnet?

282
Juliet

Sie modellieren die Zeitfunktion für die Berechnung von Fib(n) als Summe der Zeit für die Berechnung von Fib(n-1) plus der Zeit für die Berechnung von Fib(n-2) plus der Zeit für deren Addition (O(1)). Dies setzt voraus, dass wiederholte Auswertungen desselben Fib(n) dieselbe Zeit in Anspruch nehmen - d. H. Es wird keine Notiz verwendet.

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

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

Sie lösen diese Wiederholungsbeziehung (z. B. mithilfe von Generierungsfunktionen) und erhalten die Antwort.

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

Basis: n = 1 ist offensichtlich

Angenommen, T(n-1) = O(2n-1)deshalb

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

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

Wie in einem Kommentar erwähnt, ist dies jedoch nicht die enge Bindung. Eine interessante Tatsache über diese Funktion ist, dass das T(n) asymptotisch ist das Gleiche als Wert von Fib(n), da beide als definiert sind

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 im Rekursionsbaum zurückgegebenen Werte, die der Anzahl der Blätter entspricht. Da jedes Blatt O(1) benötigt, um zu berechnen, ist T(n) gleich Fib(n) x O(1). Folglich ist die enge Bindung für diese Funktion die Fibonacci-Sequenz selbst (~ θ(1.6n)). Sie können dies herausfinden, indem Sie die oben erwähnten Generierungsfunktionen verwenden.

343
Mehrdad Afshari

Fragen Sie sich einfach, wie viele Anweisungen ausgeführt werden müssen, damit F(n) abgeschlossen werden kann.

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

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

Welche Funktion erfüllt also diese Regeln? Versuchen Sie es mit einemn (a> 1):

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

Teilen Sie sich durch ein(n-2):

ein2 == a + 1

Lösen Sie nach a und Sie erhalten (1+sqrt(5))/2 = 1.6180339887, auch bekannt als goldener Quotient .

Es dauert also exponentielle Zeit.

114
Jason Cohen

Es gibt eine sehr nette Diskussion dieses spezifischen Problems bei MIT . Auf Seite 5 weisen sie darauf hin, dass, wenn Sie davon ausgehen, dass eine Addition eine Recheneinheit benötigt, die zur Berechnung von Fib (N) erforderliche Zeit sehr eng mit dem Ergebnis von Fib (N) zusammenhängt.

Daher können Sie direkt zur sehr nahen Näherung der Fibonacci-Serie springen:

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

und sagen Sie daher, dass die Leistung des naiven Algorithmus im ungünstigsten Fall ist 

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

PS: Es gibt eine Diskussion über den closed-Form-Ausdruck der N-ten Fibonacci-Nummer bei Wikipedia, wenn Sie weitere Informationen wünschen.

28
Bob Cross

Ich stimme mit pgaur und rickerbh überein, die Komplexität des rekursiven Fibonaccis ist O (2 ^ n).

Zu dieser Schlussfolgerung kam ich mit einer ziemlich simplen, aber ich glaube noch immer gültigen Argumentation.

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

Wenn also F() für eine Zahl n aufgerufen wird, wächst die Anzahl der Aufrufe von F() für eine gegebene Zahl zwischen 0 und n-1, wenn wir uns 0 nähern.

Als erster Eindruck scheint es mir, dass, wenn wir es auf eine visuelle Weise formulieren, eine Einheit pro Zeit gezeichnet wird F() für eine gegebene Zahl, nass eine Art Pyramidenform bekommt (das heißt, wenn wir zentrieren Einheiten horizontal). Etwas wie das:

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

Nun stellt sich die Frage, wie schnell sich die Basis dieser Pyramide mit wachsendem n vergrößert.

Nehmen wir einen echten 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 ist, was für diesen Fallfall 2 ^ (n-1) ist.

Nun möchten wir wissen, wie oft F(x) überhaupt aufgerufen wird, und wir können sehen, wie oft F(0) aufgerufen wird, ist nur ein Teil davon. 

Wenn wir alle * s von F(6) bis F(2) in die Zeile F(1) verschieben, sehen wir, dass F(1) und F(0) Zeilen sind jetzt gleich lang. Das heißt, total times F() wird aufgerufen, wenn n = 6 2x32 = 64 = 2 ^ 6 ist.

Nun, in Bezug auf die Komplexität:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
26
J.P.

Sie können es erweitern und haben eine Visualisierung 

     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)
15
Tony Tannous

Sie wird am unteren Ende von 2^(n/2) und am oberen Ende von 2 ^ n begrenzt (wie in anderen Kommentaren angegeben). Und eine interessante Tatsache dieser rekursiven Implementierung ist, dass es eine enge asymptotische Bindung von Fib (n) selbst gibt. Diese Fakten können zusammengefasst werden:

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

Die enge Bindung kann mit ihrer geschlossenen Form wenn Sie möchten, weiter reduziert werden.

9
Dave L.

Die Beweisantworten sind gut, aber ich muss immer ein paar Iterationen von Hand machen, um mich wirklich zu überzeugen. Also zeichnete ich einen kleinen Aufrufbaum auf meinem Whiteboard und begann die Knoten zu zählen. Ich teile meine Zählungen in Gesamtknoten, Blattknoten und Innenknoten auf. Hier ist was ich habe:

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

Was sofort springt, ist, dass die Anzahl der Blattknoten fib(n) ist. Nach einigen weiteren Iterationen wurde festgestellt, dass die Anzahl der inneren Knoten fib(n) - 1 ist. Daher ist die Gesamtanzahl der Knoten 2 * fib(n) - 1.

Da Sie die Koeffizienten bei der Klassifizierung der rechnerischen Komplexität löschen, lautet die abschließende Antwort θ(fib(n)).

9
benkc

Die zeitliche Komplexität des rekursiven Algorithmus kann durch Zeichnen des Rekursionsbaums besser geschätzt werden. In diesem Fall wäre die Rekursionsbeziehung zum Zeichnen des Rekursionsbaums T (n) = T (n-1) + T (n-2) + O (1) .__ Beachten Sie, dass für jeden Schritt O(1) eine konstante Zeit benötigt wird, da er nur einen Vergleich zum Überprüfen des Werts von n in if block.Recursionsbaum vornimmt

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

Angenommen, jede Ebene des obigen Baums wird mit i bezeichnet.

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)

angenommen, bei einem bestimmten Wert von i endet der Baum, dieser Fall wäre dann, wenn ni = 1 ist, also i = n-1, was bedeutet, dass die Höhe des Baums n-1 .. ist. Nun wollen wir sehen, wie viel Arbeit ist wird für jede der n Schichten im Baum ausgeführt. Beachten Sie, dass jeder Schritt O(1) Zeit in Anspruch nimmt, wie in der Wiederholungsbeziehung angegeben.

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

da i = n-1 ist, wird die Höhe der Baumarbeit auf jeder Ebene erledigt

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

Die Gesamtarbeit wird also die Summe der auf jeder Ebene geleisteten Arbeit sein, daher ist es 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1), da i = n-1 ist. Bei geometrischen Reihen ist diese Summe 2 ^ n, daher ist die Gesamtzeitkomplexität hier O (2 ^ n)

5
nikhil kekan

Nun, meiner Meinung nach ist dies O(2^n), da in dieser Funktion nur Rekursion die beträchtliche Zeit in Anspruch nimmt (Teilen und Erobern). Wir sehen, dass die obige Funktion in einem Baum fortgesetzt wird, bis sich die Blätter nähern, wenn wir die Ebene F(n-(n-1)) erreichen, d. H. F(1). Wenn wir hier die Zeitkomplexität notieren, die bei jeder Baumtiefe auftritt, lautet die Summationsreihe:

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

das ist die Reihenfolge von 2^n [ O(2^n) ].

2
pgaur
1
nsh3

Die naive Rekursionsversion von Fibonacci ist aufgrund von Wiederholungen in der Berechnung exponentiell:

An der Wurzel rechnen Sie:

F(n) depends on F(n-1) and F(n-2)

F(n-1) depends on F(n-2) again and F(n-3)

F(n-2) depends on F(n-3) again and F(n-4)

wenn Sie auf jeder Ebene 2 rekursive Aufrufe haben, die viele Daten in der Berechnung verschwenden, sieht die Zeitfunktion folgendermaßen aus:

T (n) = T(n-1) + T(n-2) + C, mit C-Konstante

T (n-1) = T(n-2) + T(n-3)> T(n-2) dann

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

...

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

Dies ist nur eine Untergrenze, die für den Zweck Ihrer Analyse ausreichen sollte, aber die Echtzeitfunktion ist ein Faktor einer Konstanten nach derselben Fibonacci-Formel, und die geschlossene Form ist bekanntermaßen exponentiell für die Goldener Schnitt.

Darüber hinaus können Sie optimierte Versionen von Fibonacci mithilfe der folgenden dynamischen Programmierung finden:

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];
}

Das ist optimiert und macht nur n Schritte, ist aber auch exponentiell.

Kostenfunktionen werden von der Eingabegröße bis zur Anzahl der Schritte definiert, um das Problem zu lösen. Wenn Sie die dynamische Version von Fibonacci sehen ( n Schritte zum Berechnen der Tabelle) oder den einfachsten Algorithmus, um zu wissen, ob eine Zahl eine Primzahl ist ( sqrt (n ) , um die gültigen Teiler der Zahl zu analysieren). Sie können denken, dass diese Algorithmen O (n) oder O (sqrt (n)) sind, aber dies ist einfach nicht wahr für Der folgende Grund: Die Eingabe in Ihren Algorithmus ist eine Zahl: n , unter Verwendung der binären Notation die Eingabegröße für eine ganze Zahl n Ist log2 (n) dann eine variable Änderung von

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

lassen Sie uns die Anzahl der Schritte in Abhängigkeit von der Eingabegröße ermitteln

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

dann betragen die Kosten Ihres Algorithmus in Abhängigkeit von der Eingabegröße:

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

und deshalb sind die Kosten exponentiell.

0
Miguel