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

Die Zeitkomplexität des rekursiven Algorithmus lässt sich besser abschätzen, wenn man einen Rekursionsbaum zeichnet. In diesem Fall wäre die Rekursionsbeziehung für das Zeichnen des Rekursionsbaums T(n)=T(n-1)+T(n-2)+O(1) Beachten Sie, dass jeder Schritt O(1) benötigt, was konstante Zeit bedeutet, da nur ein Vergleich durchgeführt wird, um den Wert von n in wenn Block.Rekursionsbaum würde wie folgt aussehen

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

Hier wird jede Ebene des obigen Baums mit i bezeichnet daher,

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. In diesem Fall wäre n-i=1, also i=n-1, was bedeutet, dass die Höhe des Baums n-1 ist. Nun wollen wir sehen, wie viel Arbeit für jede der n Schichten des Baumes anfällt, wobei jeder Schritt gemäß der Rekursionsbeziehung O(1) Zeit benötigt.

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, ist die auf jeder Ebene geleistete Arbeit

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

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

Answer 2

Die Probelösungen sind gut, aber ich muss immer ein paar Iterationen von Hand machen, um mich wirklich zu überzeugen. Also zeichnete ich einen kleinen Aufrufbaum auf mein Whiteboard und begann, die Knoten zu zählen. Ich teilte meine Zählungen in Gesamtknoten, Blattknoten und Innenknoten auf. Hier ist das Ergebnis:

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 auffällt, ist, dass die Anzahl der Blattknoten fib(n) . Es bedurfte einiger weiterer Iterationen, um festzustellen, dass die Anzahl der inneren Knoten fib(n) - 1 . Daher ist die Gesamtzahl der Knoten 2 * fib(n) - 1 .

Da man die Koeffizienten bei der Klassifizierung der rechnerischen Komplexität weglässt, lautet die endgültige Antwort (fib(n)) .

Answer 3

Sie wird am unteren Ende begrenzt durch 2^(n/2) und am oberen Ende um 2^n (wie in anderen Kommentaren erwähnt). Und eine interessante Tatsache dieser rekursiven Implementierung ist, dass sie eine enge asymptotische Schranke von Fib(n) selbst hat. Diese Fakten lassen sich zusammenfassen:

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

Die enge Schranke kann weiter reduziert werden, indem ihre geschlossene Form wenn Sie mögen.

Answer 4

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

An der Wurzel rechnest du:

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

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

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

dann haben Sie auf jeder Ebene 2 rekursive Aufrufe, die eine Menge Daten in der Berechnung verschwenden, die Zeitfunktion wird wie folgt aussehen:

T(n) = T(n-1) + T(n-2) + C, wobei C konstant ist

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 untere Grenze, die für den Zweck Ihrer Analyse ausreichen sollte, aber die Echtzeitfunktion ist ein Faktor einer Konstanten durch die gleiche Fibonacci-Formel und die geschlossene Form ist bekanntlich ein Exponentialwert des Goldenen Schnitts.

Darüber hinaus können Sie optimierte Versionen von Fibonacci finden, indem Sie dynamische Programmierung wie diese verwenden:

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, sondern ist 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 ( n Schritte zur Berechnung der Tabelle) oder der einfachste Algorithmus zur Feststellung, ob eine Zahl eine Primzahl ist ( sqrt(n) um die gültigen Teiler der Zahl zu analysieren). Sie könnten denken, dass diese Algorithmen O(n) o O(sqrt(n)) aber das ist aus folgendem Grund einfach nicht richtig: Die Eingabe für Ihren Algorithmus ist eine Zahl: n Bei Verwendung der binären Notation ist die Eingabegröße für eine ganze Zahl n est log2(n) dann eine variable Änderung von

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

Ermitteln Sie die Anzahl der Schritte in Abhängigkeit von der Eingabegröße

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.

Answer 5

Sie ist einfach zu berechnen, indem Funktionsaufrufe grafisch dargestellt werden. Addieren Sie einfach die Funktionsaufrufe für jeden Wert von n und schauen 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 an, wenn wir n erhöhen.

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

Es besteht keine Notwendigkeit für eine Reihe komplexer mathematischer Berechnungen. Zeichnen Sie einfach die untenstehenden Funktionsaufrufe auf und passen Sie eine Funktion an die Zahlen an.

Wenn Sie mit dem Goldenen Schnitt vertraut sind, werden Sie ihn auch als solchen erkennen.

Diese Antwort ist richtiger als die akzeptierte Antwort, die behauptet, dass sie sich f(n) = 2^n nähert. Das wird sie nie. Sie 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)