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

Nun, meiner Meinung nach ist es O(2^n) da bei dieser Funktion nur die Rekursion die meiste Zeit in Anspruch nimmt (divide et conquer). Wir sehen, dass sich die obige Funktion in einem Baum fortsetzt, bis sich die Blätter nähern, wenn wir die Ebene F(n-(n-1)) d.h. F(1) . Wenn wir also die Zeitkomplexität für jede Tiefe des Baumes aufschreiben, ergibt sich die folgende Summenreihe:

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

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

Answer 2

Keine Antwort betont die wahrscheinlich schnellste und speichereffizienteste Methode zur Berechnung der Sequenz. Es gibt einen exakten Ausdruck in geschlossener Form für die Fibonacci-Folge. Er kann mit Hilfe von erzeugenden Funktionen oder mit linearer Algebra gefunden werden, wie ich es jetzt tun werde.

Sea f_1,f_2, ... sei die Fibonacci-Folge mit f_1 = f_2 = 1 . Betrachten wir nun eine Folge von zweidimensionalen Vektoren

f_1  ,  f_2  ,  f_3  ,  ...
f_2  ,  f_3  ,  f_4  ,  ...

Beachten Sie, dass das nächste Element v_{n+1} in der Vektorfolge ist M.v_{n} wobei M eine 2x2-Matrix ist, die durch

M = [0 1]
    [1 1]

aufgrund von f_{n+1} = f_{n+1} and f_{n+2} = f_{n} + f_{n+1}

M ist diagonalisierbar über den komplexen Zahlen (eigentlich auch diagonalisierbar über den reellen Zahlen, aber das ist normalerweise nicht der Fall). Es gibt zwei verschiedene Eigenvektoren von M, die durch

1      1
x_1    x_2

wobei x_1 = (1+sqrt(5))/2 und x_2 = (1-sqrt(5))/2 die verschiedenen Lösungen der Polynomgleichung sind x*x-x-1 = 0 . Die entsprechenden Eigenwerte sind x_1 und x_2. Stellen Sie sich M als eine lineare Transformation vor und ändern Sie Ihre Basis, um zu sehen, dass sie äquivalent ist zu

 D = [x_1  0]
     [0  x_2]

Um f_n zu finden, muss man v_n finden und sich die erste Koordinate ansehen. Um v_n zu finden, wende M n-1 mal auf v_1 an. Aber die Anwendung von M n-1 mal ist einfach, denken Sie einfach an D. Dann kann man mit Hilfe der Linearität finden

f_n = 1/sqrt(5)*(x_1^n-x_2^n)

Da die Norm von x_2 kleiner als 1 ist, verschwindet der entsprechende Term, wenn n gegen unendlich tendiert; daher reicht es aus, die größte ganze Zahl kleiner als (x_1^n)/sqrt(5) zu erhalten, um die Antwort genau zu finden. Mit dem Trick des wiederholten Quadrierens kann dies mit nur O(log_2(n)) Multiplikations- (und Additions-) Operationen. Die Speicherkomplexität ist sogar noch beeindruckender, weil sie so implementiert werden kann, dass immer höchstens eine Zahl im Speicher gehalten werden muss, deren Wert kleiner als die Antwort ist. Da es sich bei dieser Zahl jedoch nicht um eine natürliche Zahl handelt, ändert sich die Speicherkomplexität, je nachdem, ob man feste Bits zur Darstellung jeder Zahl verwendet (und daher Berechnungen mit Fehlern durchführt) (O(1)-Speicherkomplexität in diesem Fall) oder ein besseres Modell wie Turing-Maschinen verwendet; in diesem Fall ist eine weitere Analyse erforderlich.