Rechenkomplexität der Fibonacci-Folge

StackOverflow https://stackoverflow.com/questions/360748

Frage

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

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

Was ist die Rechenkomplexität der Fibonacci-Folge und wie wird er berechnet?

War es hilfreich?

Lösung

Sie die Zeitfunktion modellieren Fib(n) als Summe von Zeit zu berechnen Fib(n-1) und die Zeit zu berechnen Fib(n-2) und die Zeit zu berechnen, sie zusammen fügen (O(1)). Dies wird unter der Annahme, dass die wiederholten Auswertungen des gleichen Fib(n) die gleiche Zeit in Anspruch nehmen - d. H kein memoization ist die Verwendung

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

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

lösen Sie diese Rekursion (unter Verwendung von Funktionen, zum Beispiel zu erzeugen), und Sie werden mit der Antwort enden.

Alternativ können Sie die Rekursionsbaum zeichnen, die Tiefe n haben und intuitiv herausfinden, dass diese Funktion asymptotisch ist O(2 n ). Anschließend können Sie Ihre Vermutung durch Induktion beweisen.

Basis: n = 1 liegt auf der Hand

Angenommen

T(n-1) = O(2 n-1 ), also

T(n) = T(n-1) + T(n-2) + O(1) , die gleich

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

Wie jedoch in einem Kommentar erwähnt, ist dies nicht die eng gebunden. Eine interessante Tatsache zu dieser Funktion ist, dass die T (n) asymptotisch ist die gleiche als der Wert von Fib(n) da beide sind definiert als

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

Die Blätter der Rekursionsbaum immer zurückkehren 1. Der Wert von Fib(n) ist die Summe aller Werte von den Blättern in der Rekursionsbaum zurückgeführt, um die Anzahl der Blätter gleich ist. Da jedes Blatt nimmt O (1) zu berechnen, ist T(n) gleich Fib(n) x O(1). Folglich ist die eng gebunden für diese Funktion die Fibonacci-Sequenz selbst (~ θ(1.6 n )). Sie können diese fest gebunden mit erzeugenden Funktionen herauszufinden, wie ich oben erwähnt habe.

Andere Tipps

Fragen Sie sich selbst, wie viele Anweisungen für F(n) ausführen müssen abzuschließen.

Für F(1), die Antwort ist 1 (der erste Teil der bedingten).

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

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

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

durch Dividieren durch a (n-2) :

a 2 == a + 1

Lösen für a und Sie (1+sqrt(5))/2 = 1.6180339887 erhalten, auch als goldenen Verhältnis .

So dauert es exponentielle Zeit.

Es ist eine sehr schöne Diskussion dieses am MIT über . Auf Seite 5, machen sie den Punkt, dass, wenn Sie davon ausgehen, dass eine Zugabe eine Recheneinheit in Anspruch nimmt, Zeit Fib (N) erforderlich zu berechnen ist sehr eng mit dem Ergebnis der Fib (N).

Als Ergebnis können Sie überspringen direkt auf die sehr enge Annäherung der Fibonacci-Reihe: 

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

und sagt daher, dass die schlimmste Fall der Leistung des naiven Algorithmus ist 

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

PS: Es gibt eine Diskussion über die geschlossene Form Ausdruck der N-te Fibonacci-Zahl über in der Wikipedia, wenn Sie würde mehr Informationen.

Ich bin mit pgaur und rickerbh, rekursive-Fibonacci Komplexität ist O (2 ^ n).

Ich kam zu dem gleichen Ergebnis kommt eine ziemlich simpel, aber ich glaube immer noch gültig Argumentation.

Als erstes geht es um herauszufinden, wie viele Male rekursive Fibonacci-Funktion (F () von jetzt an) aufgerufen wird, wenn die n-te Fibonacci-Zahl zu berechnen. Wenn es einmal pro Zahl in der Folge 0 bis n aufgerufen wird, dann haben wir O (n), wenn es aufgerufen wird n-mal für jede Zahl, dann bekommen wir O (n * n) oder O (n ^ 2), und so weiter.

Also, wenn F () für eine Anzahl n aufgerufen wird, wird die Anzahl der F () für eine gegebene Zahl zwischen 0 bezeichnet und n-1 wächst, wie wir 0 nähern.

Als erster Eindruck, scheint es mir, dass, wenn wir sie in einer visuellen Art und Weise ausgedrückt, eine Einheit pro Zeit Zeichnung F () für eine gegebene Zahl genannt wird, nass eine Art Pyramidenform erhalten (das heißt, wenn wir Zentrieren Einheiten horizontal). So etwas wie folgt aus: 

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

Nun, die Frage ist, wie schnell ist die Basis dieser Pyramide Erweiterung als n wächst?

Lassen Sie sich einen realen Fall nehmen, 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, F (0) 32 Mal aufgerufen wird, die 2 ^ 5 ist, die für diese Probe Fall ist 2 ^ (n-1).

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

Wenn wir geistig bewegen die ganze * 's von F (6) bis F (2) Linien in F (1) Linie sehen wir, dass F (1) und F (0) Linien sind nun gleich lang. Was bedeutet, Gesamtzeiten f () wird aufgerufen, wenn n = 6 ist 2x32 = 64 = 2 ^ 6.

Nun, in Bezug auf die Komplexität: 

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

Sie können es erweitern und eine Visualisierung 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)

Es ist auf dem unteren Ende durch 2^(n/2) begrenzt und am oberen Ende durch 2 ^ n (wie in anderen Kommentaren vermerkt). Und eine interessante Tatsache, dass rekursive Implementierung ist, dass es eine enge asymptotisch hat gebunden von Fib (n) selbst. 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 weiter reduziert werden seine mit geschlossener Form wenn Sie möchten.

Der Beweis Antworten sind gut, aber ich habe immer ein paar Wiederholungen von Hand zu tun, um mich wirklich zu überzeugen. So zog ich auf meiner Tafel einen kleinen Berufung Baum heraus und fing an, die Knoten zu zählen. Ich teile meine zählt hinaus in insgesamt Knoten, Blattknoten und innere Knoten. 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 aus, dass die Anzahl von Blattknoten ist fib(n). Was hat ein paar mehr Iterationen ist zu bemerken, dass die Anzahl der inneren Knoten ist fib(n) - 1. Daher ist die Gesamtzahl der Knoten ist 2 * fib(n) - 1.

Da Sie die Koeffizienten fallen, wenn die Berechnungskomplexität zu klassifizieren, die endgültige Antwort ist θ(fib(n)).

rekursive Algorithmus Zeitkomplexität besser abgeschätzt durch Ziehen Rekursionsbaum werden kann, in diesem Fall die Rekursion Rekursionsbaum zum Zeichnen wäre T (n) = T (n-1) + T (n-2) + O (1 ) beachten Sie, dass jeder Schritt O (1), was bedeutet konstante Zeit in Anspruch nimmt, da es nur ein Vergleich tut Wert von n zu prüfen, in , wenn block.Recursion Baum aussieht

würde 
          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

lässt sich hier sagen, jede Ebene von oben Baum durch i bezeichnet wird 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)

kann bei bestimmtem Wert von i sagen, der Baum endet, würde dieser Fall sein, wenn n-i = 1, also i = n-1, was bedeutet, dass die Höhe des Baumes ist n-1. Schauen wir uns nun sehen, wie viel Arbeit für jeden von n Schichten in tree.Note getan wird, dass jeder Schritt, wie in Rekursion angegeben O (1) Zeit in Anspruch nimmt. 

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 in der Höhe des Baumes Arbeit auf jeder Ebene getan werden 

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

Daher Gesamtarbeit wird auf jeder Ebene durchgeführt Summe der geleisteten Arbeit, daher wird es 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1), da i = n -1. Durch die geometrische Reihe dieser Summe ist 2 ^ n, also die Gesamtzeit Komplexität hier O (2 ^ n)

Nun, für mich nach wie es in dieser Funktion O(2^n) nur Rekursion ist die beträchtliche Zeit nehmen (teile und herrsche). Wir sehen, dass die obige Funktion in einem Baum fortgesetzt wird, bis die Blätter Ansätze sind, wenn wir das heißt F(n-(n-1)) auf das Niveau F(1) erreichen. Also, hier, wenn wir die Zeitkomplexität in jeder Tiefe des Baumes angetroffen notierten, die Summe Serie ist: 

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

das ist, um von 2^n [ O(2^n) ].

Die naive Rekursion Version von Fibonacci ist exponentiell von Design aufgrund der Wiederholung in der Berechnung:

An der Wurzel Sie Berechnung:

F (n) abhängig von F (n-1) und F (n-2)

F (n-1) ist abhängig von F (n-2) wieder und F (n-3)

F (n-2) ist abhängig von F (n-3) wieder und F (n-4)

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

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

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 Schranke, die zum Zweck der Analyse sollte ausreichen, aber die Echtzeit-Funktion ist ein Faktor einer Konstante, die durch die gleiche Fibonacci-Formel und der geschlossene Form exponentiell des goldenen Schnitts zu sein, ist bekannt.

Darüber hinaus können Sie Versionen von Fibonacci optimiert finden Verwendung dynamischer Programmierung wie folgt aus: 

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 tun nur n Schritte aber auch exponentiell.

Kostenfunktionen werden von Eingangsgröße auf die Anzahl der Schritte definiert, das Problem zu lösen. Wenn Sie die dynamische Version der Fibonacci ( n Schritte, um die Tabelle zu berechnen) zu sehen oder die einfachste Algorithmus zu wissen, ob eine Zahl eine Primzahl ist ( sqrt (n) , um die Gültigkeit zu analysieren Teiler der Zahl). Sie mögen denken, dass diese Algorithmen sind O (n) oder O (sqrt (n)) , aber dies aus folgenden Gründen einfach nicht wahr ist: Der Eingang zu Ihrem Algorithmus ist eine Zahl: n , mit der binären Schreibweise der Eingangsgröße für eine ganze Zahl n ist log2 (n) dann tun eine variable Änderung von 

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

lassen die Anzahl der Schritte in Abhängigkeit von der Eingangsgröße herauszufinden 

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

dann die Kosten Ihres Algorithmus in Abhängigkeit von der Eingangsgröße ist: 

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

und deshalb die Kosten für eine exponentielles sind.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top