Rechenkomplexität der Fibonacci-Sequenz

330

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

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

Julia
quelle
3
Siehe den Abschnitt zum Matrixformular hier: en.wikipedia.org/wiki/Fibonacci_number . Mit dieser Matrix ^ n (auf clevere Weise) können Sie Fib (n) in O (lg n) berechnen. Der Trick besteht darin, die Power-Funktion auszuführen. Es gibt einen sehr guten Vortrag auf iTunesU über genau dieses Problem und wie man es in O (lg n) löst. Der Kurs ist eine Einführung in Algorithmen aus MIT-Vorlesung 3 (es ist absolut kostenlos, also probieren Sie es aus, wenn Sie interessiert sind)
Aly
1
Keiner der obigen Kommentare befasst sich mit der Frage, die sich auf die rechnerische Komplexität der naiven Version (im veröffentlichten Code) bezieht, nicht auf intelligentere Versionen wie Matrixform oder nicht rekursive Berechnung.
Josh Milthorpe
Ein sehr schönes Video hier, das sowohl die Komplexität der unteren Grenze (2 ^ n / 2) als auch die Komplexität der oberen Grenze (2 ^ n) der rekursiven Implementierung behandelt.
RBT
1
Eine Randnotiz-Abfrage: Sollte die naive Implementierung der Fibonacci-Reihe iterativ oder rekursiv sein ?
RBT

Antworten:

374

Sie modellieren die zu berechnende Zeitfunktion Fib(n)als Summe der zu berechnenden Zeit Fib(n-1)plus der zu berechnenden Zeit Fib(n-2)plus der Zeit, um sie zu addieren ( O(1)). Dies setzt voraus, dass wiederholte Auswertungen derselben Fib(n)dieselbe Zeit in Anspruch nehmen - dh es wird keine Memoisierung 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 zeichnen, der Tiefe hat nund intuitiv herausfindet, dass diese Funktion asymptotisch ist . Sie können dann Ihre Vermutung durch Induktion beweisen.O(2n)

Basis: n = 1ist offensichtlich

Es sei angenommen , deshalbT(n-1) = O(2n-1)

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 Grenze. Eine interessante Tatsache über diese Funktion ist, dass T (n) asymptotisch der gleiche Wert ist wie der 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 Werte, die von den Blättern im Rekursionsbaum zurückgegeben werden, was der Anzahl der Blätter entspricht. Da jedes Blatt O (1) zur Berechnung benötigt, T(n)ist es gleich Fib(n) x O(1). Folglich ist die enge Grenze für diese Funktion die Fibonacci-Sequenz selbst (~ ). Sie können diese enge Grenze herausfinden, indem Sie die oben erwähnten Generierungsfunktionen verwenden.θ(1.6n)

Mehrdad Afshari
quelle
29
Auch Beweis durch Induktion. Nett. +1
Andrew Rollings
Obwohl die Grenze nicht fest ist.
Kapitän Segfault
@ Captain Segfault: Ja. Ich habe die Antwort geklärt. Sie würden die enge Bindung mit der GF-Methode bekommen, wie ich oben geschrieben hatte.
Mehrdad Afshari
Nehmen Sie Ihre StackOverflowException als Witz. Die Exponentialzeit ist mit eher kleinen Werten für n recht leicht wahrnehmbar.
David Rodríguez - Dribeas
1
"Alternativ können Sie den Rekursionsbaum zeichnen, der die Tiefe n hat, und intuitiv herausfinden, dass diese Funktion asymptotisch O (2n) ist." - Das ist völlig falsch. Die zeitliche Komplexität ist O (golden_ratio ^ n). Es kommt O (2 ^ n) nie nahe. Wenn Sie in Richtung Unendlichkeit greifen könnten, würde es nahe an O (golden_ratio ^ n) kommen. Das ist, was eine Asymptote ist, der Abstand zwischen den beiden Linien muss sich 0 nähern.
Bob
133

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

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

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

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

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

Teilen Sie durch a (n-2) :

a 2 == a + 1

Löse nach aund du bekommst (1+sqrt(5))/2 = 1.6180339887, auch bekannt als der goldene Schnitt .

Es dauert also exponentiell.

Jason Cohen
quelle
8
Beweis durch Induktion. Nett. +1
Andrew Rollings
2
30 Upvotes für eine falsche Antwort? :-) Folgt daraus, dass 1 = F (1) = (1 + sqrt (5)) / 2? Und was ist mit der anderen Lösung (1-sqrt (5)) / 2?
Carsten S
1
Nein, 1 ist nicht gleich 1 + 1. Die Funktion, die diese Regeln erfüllt, wird in der Frage erwähnt.
Molbdnilo
6
Die Antwort ist nicht falsch. Es ist asymptomatisch richtig. Die andere Lösung ist negativ und macht physikalisch keinen Sinn.
Da Teng
10
Kann jemand erklären, wie a ^ n == a ^ (n-1) + a ^ (n-2) diese Regeln erfüllen? Wie ist es genau zufrieden, bitte genau sein.
Frank
33

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

Ich bin durch eine eher vereinfachte, aber meiner Meinung nach immer noch gültige Argumentation zu dem gleichen Schluss gekommen.

Zunächst geht es darum herauszufinden, wie oft die rekursive Fibonacci-Funktion (F () von nun an) bei der Berechnung der N-ten Fibonacci-Zahl aufgerufen wird. Wenn es einmal pro Nummer in der Folge 0 bis n aufgerufen wird, dann haben wir O (n), wenn es für jede Nummer n-mal aufgerufen wird, 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 Häufigkeit, mit der F () für eine gegebene Zahl zwischen 0 und n-1 aufgerufen wird, wenn wir uns 0 nähern.

Als ersten Eindruck scheint es mir, dass, wenn wir es visuell formulieren, das Zeichnen einer Einheit pro Mal, wenn F () für eine bestimmte Zahl aufgerufen wird, nass eine Art Pyramidenform erhält (dh wenn wir Einheiten horizontal zentrieren) ). Etwas wie das:

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 ist, was für diesen Beispielfall 2 ^ (n-1) ist.

Nun wollen 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 mental alle * von F (6) nach F (2) in die Linie F (1) verschieben, sehen wir, dass die Linien F (1) und F (0) jetzt gleich lang sind. Das heißt, die Gesamtzeit, zu der F () aufgerufen wird, wenn n = 6 2x32 = 64 = 2 ^ 6 ist.

Nun zur Komplexität:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
JP
quelle
3
F (3) wird nur dreimal und nicht viermal aufgerufen. Die zweite Pyramide ist falsch.
Avik
2
F (3) = 3, F (2) = 5, F (1) = 8, F (0) = 5. Ich würde es beheben, aber ich glaube nicht, dass ich diese Antwort mit einer Bearbeitung retten kann.
Bernhard Barker
31

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

Infolgedessen können Sie direkt zur sehr engen Annäherung der Fibonacci-Reihe springen:

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

und sagen Sie daher, dass die schlechteste Leistung des naiven Algorithmus ist

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

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

Bob Cross
quelle
Danke für den Kurslink. Sehr schöne Beobachtung auch
SwimBikeRun
16

Sie können es erweitern und eine Visulisierung haben

     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)
Tony Tannous
quelle
1
Ich verstehe die erste Zeile. Aber warum gibt es <am Ende einen weniger als Charakter ? Wie bist du gekommen T(n-1) + T(n-1)?
Quazi Irfan
@ QuaziIrfan: D das ist ein Pfeil. -> [(nicht weniger als). Entschuldigung für die Verwirrung in Bezug auf die letzte Zeile]. Für die erste Zeile, T(n-1) > T(n-2)na ja ... Also kann ich mich ändern T(n-2)und setzen T(n-1). Ich werde nur eine höhere Grenze bekommen, die noch gültig ist fürT(n-1) + T(n-2)
Tony Tannous
10

Es wird am unteren Ende durch 2^(n/2)und am oberen Ende durch 2 ^ n begrenzt (wie in anderen Kommentaren angegeben). Und eine interessante Tatsache dieser rekursiven Implementierung ist, dass sie eine enge asymptotische Grenze von Fib (n) selbst aufweist. 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 weiter reduziert werden , wenn Sie möchten.

Dave L.
quelle
10

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

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 herausspringt, ist, dass die Anzahl der Blattknoten ist fib(n). Was einige weitere Iterationen dauerte, um festzustellen, ist die Anzahl der inneren Knoten fib(n) - 1. Daher ist die Gesamtzahl der Knoten 2 * fib(n) - 1.

Da Sie die Koeffizienten bei der Klassifizierung der Rechenkomplexität fallen lassen, lautet die endgültige Antwort θ(fib(n)).

benkc
quelle
(Nein, ich habe keinen vollständigen 10-tiefen
Anrufbaum
Schön, ich habe mich gefragt, wie viele zusätzliche rekursive Fib-Ergänzungen vorgenommen haben. Es ist nicht nur das Hinzufügen 1zu einer einzelnen Akkumulatorzeit Fib(n), sondern auch interessant, dass es immer noch genau ist θ(Fib(n)).
Peter Cordes
Beachten Sie, dass einige (die meisten) rekursiven Implementierungen Zeit mit dem Hinzufügen verbringen 0: Rekursionsbasisfälle sind 0und 1, weil sie es tun Fib(n-1) + Fib(n-2). Daher ist die Antwort3 * Fib(n) - 2 aus dieser Nur-Link-Antwort wahrscheinlich genauer für die Gesamtzahl der Knoten, nicht 2 * Fib(n) - 1.
Peter Cordes
Ich kann nicht die gleichen Ergebnisse auf den Blattknoten erzielen. Ausgehend von 0: F (0) -> 1 Blatt (selbst); F (1) -> 1 Blatt (selbst); F (2) -> 2 Blätter (F (1) und F (0)); F (3) -> 3 Blätter; F (5) -> 8 Blätter; usw.
alexlomba87
9

Die zeitliche Komplexität des rekursiven Algorithmus kann besser geschätzt werden, indem ein Rekursionsbaum gezeichnet wird. In diesem Fall wäre die Wiederholungsrelation für das Zeichnen eines Rekursionsbaums T (n) = T (n-1) + T (n-2) + O (1) Jeder Schritt benötigt O (1), was eine konstante Zeit bedeutet, da nur ein Vergleich durchgeführt wird, um den Wert von n in if block zu überprüfen. Der Rekursionsbaum würde so aussehen

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

Nehmen wir an, jede Ebene des obigen Baums wird daher 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)

Nehmen wir an, bei einem bestimmten Wert von i endet der Baum. Dieser Fall wäre, wenn ni = 1 ist, also i = n-1, was bedeutet, dass die Höhe des Baums n-1 ist. Lassen Sie uns nun sehen, wie viel Arbeit für jede der n Ebenen im Baum erledigt wird. Beachten Sie, dass jeder Schritt O (1) Zeit benötigt, wie in der Wiederholungsrelation 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 die Höhe des Baumes ist, wird die auf jeder Ebene geleistete Arbeit ausgeführt

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

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

nikhil kekan
quelle
2

Nun, meiner Meinung nach ist es so, O(2^n)als ob in dieser Funktion nur die 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 das Niveau erreichen, F(n-(n-1))dh F(1). Wenn wir also die Zeitkomplexität aufschreiben, die in 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) ].

pgaur
quelle
1

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

An der Wurzel berechnen Sie:

F (n) hängt von F (n-1) und F (n-2) ab

F (n-1) hängt wieder von F (n-2) ab und F (n-3)

F (n-2) hängt wieder von F (n-3) ab und F (n-4)

Wenn Sie dann 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 konstanter C.

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 den Goldenen Schnitt.

Darüber hinaus können Sie optimierte Versionen von Fibonacci mit dynamischer Programmierung wie folgt 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 zur Lösung des Problems definiert. Wenn Sie die dynamische Version von Fibonacci sehen ( n Schritte zum Berechnen der Tabelle) oder den einfachsten Algorithmus, um festzustellen, 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 aus folgendem Grund einfach nicht wahr: Die Eingabe in Ihren Algorithmus ist eine Zahl: n , wobei die binäre Notation die Eingabegröße für a verwendet Ganzzahl n ist log2 (n) und führt dann eine Variablenänderung von durch

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

Lassen Sie uns die Anzahl der Schritte als Funktion der Eingabegröße herausfinden

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

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

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

und deshalb sind die Kosten exponentiell.

Miguel
quelle
1

Es ist einfach zu berechnen, indem Funktionsaufrufe grafisch dargestellt werden. Fügen Sie einfach die Funktionsaufrufe für jeden Wert von n hinzu und sehen Sie, wie die Zahl wächst.

Das große O ist O (Z ^ n), wobei Z der goldene Schnitt oder etwa 1,62 ist.

Sowohl die Leonardo-Zahlen als auch die Fibonacci-Zahlen nähern sich diesem Verhältnis, wenn wir n erhöhen.

Im Gegensatz zu anderen Big O-Fragen gibt es keine Variabilität in der Eingabe und sowohl der Algorithmus als auch die Implementierung des Algorithmus sind klar definiert.

Es ist keine Menge komplexer Mathematik erforderlich. Stellen Sie einfach die folgenden Funktionsaufrufe dar und passen Sie eine Funktion an die Zahlen an.

Oder wenn Sie mit dem Goldenen Schnitt vertraut sind, werden Sie ihn als solchen erkennen.

Diese Antwort ist korrekter als die akzeptierte Antwort, die behauptet, dass sie sich f (n) = 2 ^ n nähert. Das wird es nie. Es wird sich f (n) = golden_ratio ^ n nähern.

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)
Bob
quelle
1
Können Sie eine Quelle für diese Behauptung über den Goldenen Schnitt angeben?
Nico Haase
-1

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

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

nsh3
quelle
4
Es ist auch schön, wenn Sie Ihre Antwort erklären könnten, anstatt nur einen Link zu posten.
Magnilex
2
Keine Erklärung angegeben
Kunal B.