wake-up-neo.com

Warum ist die Komplexität der Berechnung der Fibonacci-Serie 2 ^ n und nicht n ^ 2?

Ich versuche die Komplexität der Fibonacci-Serie mithilfe eines Rekursionsbaums zu finden und schlussfolgerte height of tree = O(n) im schlimmsten Fall cost of each level = cn, daher complexity = n*n=n^2

Wie kommt es O(2^n)?

24
Suri

Die Komplexität eines naiven rekursiven Fibonacci beträgt in der Tat 2ⁿ.

T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) = 
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...

In jedem Schritt rufen Sie T zweimal auf und bieten so eine mögliche asymptotische Barriere für:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ

Bonus : Die beste theoretische Implementierung für Fibonacci ist eigentlich ein enge Formel unter Verwendung des goldenen Schnitts :

Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]

(Es leidet jedoch an Genauigkeitsfehlern im wirklichen Leben aufgrund von Gleitkomma-Arithmetik, die nicht genau sind.)

33
amit

Der Rekursionsbaum für fib (n) würde ungefähr so ​​aussehen:

                              n       
                           /     \
                          n-1    n-2      --------- maximum 2^1 additions
                         /  \    /   \
                       n-2   n-3 n-3 n-4  -------- maximum 2^2 additions
                      /   \           
                     n-3 n-4              -------- maximum 2^3 additions         
                                                ........
                                          -------- maximum 2^(n-1) additions  
  1. Verwenden von n-1 in 2 ^ (n-1), da wir für fib (5) schließlich auf fib (1) gehen werden
  2. Anzahl der internen Knoten = Anzahl der Blätter - 1 = 2 ^ (n-1) - 1 
  3. Anzahl der Zugaben = Anzahl der internen Knoten + Anzahl der Blätter = (2 ^ 1 + 2 ^ 2 + 2 ^ 3 + ...) + 2 ^ (n-1)
  4. Wir können die Anzahl der internen Knoten durch 2 ^ (n-1) - 1 ersetzen, da sie immer unter diesem Wert liegt: = 2 ^ (n-1) -1 + 2 ^ (n-1). ~ 2 ^ n
13
Anum Malik

t (n) = t (n-1) + t (n-2) die durch Baummethode gelöst werden kann:

                                  t(n-1)  +  t(n-2)        2^1=2
                                   |         |  
                            t(n-2)+t(n-3)  t(n-3)+t(n-4)   2^2=4  
                                .               .          2^3=8
                                .               .           .
                                .               .           .

Ähnlich für die letzte Ebene. . 2 ^ n
es wird Gesamtzeitkomplexität => 2 + 4 + 8 + ..... 2 ^ n Nach dem Lösen des obigen gp erhalten wir Zeitkomplexität als O (2 ^ n) 

6
mukesh

Schau es dir so an. Angenommen, die Komplexität der Berechnung von F(k), der kth Fibonacci-Zahl, durch Rekursion ist höchstens 2^k für k <= n. Dies ist unsere Induktionshypothese. Die Komplexität der Berechnung von F(n + 1) durch Rekursion ist dann 

F(n + 1) = F(n) + F(n - 1)

die Komplexität hat 2^n + 2^(n - 1). Beachten Sie, dass

2^n + 2^(n - 1) = 2 * 2^n / 2 + 2^n / 2 = 3 * 2^n / 2 <= 2 * 2^n = 2^(n + 1).

Wir haben durch Induktion gezeigt, dass die Behauptung, dass die Berechnung von F(k) durch Rekursion höchstens 2^k ist, richtig ist.

6
jason

Sie haben Recht, dass die Tiefe des Baums O (n) ist, aber Sie arbeiten nicht auf jeder Ebene mit O(n). Auf jeder Ebene arbeiten Sie O(1) pro rekursivem Aufruf, aber jeder rekursive Aufruf trägt dann zwei neue rekursive Aufrufe bei, einen auf der Ebene darunter und einen auf der Ebene zwei darunter. Dies bedeutet, dass die Anzahl der Anrufe pro Ebene exponentiell ansteigt, je weiter Sie im Rekursionsbaum voranschreiten.

Interessanterweise können Sie die genaue Anzahl der Anrufe festlegen, die erforderlich sind, um F(n) als 2F (n + 1) - 1 zu berechnen, wobei F(n) die n-te Fibonacci-Zahl ist. Das können wir induktiv beweisen. Um F(0) oder F (1) zu berechnen, müssen wir als Basisfall genau einen Aufruf der Funktion ausführen, die beendet wird, ohne neue Aufrufe vorzunehmen. Angenommen, L(n) ist die Anzahl der Aufrufe, die zur Berechnung von F (n) erforderlich sind. Dann haben wir das

L (0) = 1 = 2 · 1 - 1 = 2F (1) - 1 = 2F (0 + 1) - 1

L (1) = 1 = 2 · 1 - 1 = 2F (2) - 1 = 2F (1 + 1) - 1

Nehmen wir nun für den induktiven Schritt an, dass für alle n '<n mit n ≥ 2 L (n') = 2F (n + 1) - 1 ist. Um dann F (n) zu berechnen, müssen wir 1 machen Aufruf der Anfangsfunktion, die F (n) berechnet, was wiederum Aufrufe von F(n-2) und F (n-1) auslöst. Durch die induktive Hypothese wissen wir, dass F(n-1) und F(n-2) in L(n-1) und L(n-2) Anrufe. Somit beträgt die Gesamtlaufzeit

1 + L (n - 1) + L (n - 2)

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

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

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

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

= 2F (n + 1) - 1

Womit die Induktion abgeschlossen ist.

An dieser Stelle können Sie Binets Formel verwenden, um dies zu zeigen

L(n) = 2(1/√5)(((1 + √5) / 2)n - ((1 - √5)/2)n) - 1

Und so ist L(n) = O (((1 + √5)/2)n). Wenn wir die Konvention verwenden, dass

φ = (1 + √5)/2 ≤ 1,6

Wir haben das

L (n) = Θ (φn)

Und da φ <2 ist, ist dies o (2n) (mit Little-O-Notation).

Interessanterweise habe ich den Namen L(n) für diese Reihe gewählt, da diese Reihe Leonardo-Zahlen heißt. Zusätzlich zu seiner Verwendung entsteht es bei der Analyse des Algorithmus smoothsort .

Hoffe das hilft!

5
templatetypedef

Die Komplexität rekursiver Fibonacci-Serien beträgt 2 ^ n:
Dies wird die Wiederholungsbeziehung für rekursive Fibonacci sein 

 T(n)=T(n-1)+T(n-2)                  No  of elements  2

Nun zum Lösen dieser Beziehung unter Verwendung der Substitutionsmethode (Ersetzen des Wertes von T(n-1) und T (n-2))

T(n)=T(n-2)+2*T(n-3)+T(n-4)          No  of elements  4=2^2

Erneut werden Werte durch den obigen Begriff ersetzt

T(n)=T(n-3)+3*T(n-4)+3*T(n-5)+T(n-6)  No  of elements  8=2^3

Nachdem wir es vollständig gelöst haben, bekommen wir

T(n)={T(n-k)+---------+---------}----------------------------->2^k  eq(3) 

Dies bedeutet, dass die maximale Anzahl rekursiver Anrufe auf keiner Ebene höchstens 2 ^ n beträgt.
Und für alle rekursiven Aufrufe in Gleichung 3 gilt ϴ (1), sodass die Komplexität der Zeit 2^n* ϴ(1)=2^n ist. 

1
Mohit Yadav

Die Komplexität der Fibonacci-Reihe ist O (F (k)), wobei F(k) die k-te Fibonacci-Zahl ist. Dies kann durch Induktion nachgewiesen werden. Es ist trivial für begründeten Fall. Und nehmen wir für alle k <= n an, die Komplexität der Berechnung von F(k) sei c * F (k) + o (F (k)), dann für k = n + 1 die Komplexität von Berechnung von F (n + 1) ist c · F (n) + o(F(n)) + c · F (n-1) + o(F(n-1)) = c * (F (n) + F(n-1)) + o(F(n)) + o(F(n-1)) = O (F (n + 1)).

1
Zhongyuan

Die O (2 ^ n) -Komplexität der Berechnung von Fibonacci-Zahlen gilt nur für den Rekursionsansatz. Mit ein wenig mehr Platz können Sie mit O (n) eine viel bessere Leistung erzielen.

public static int fibonacci(int n) throws Exception {

  if (n < 0)
    throws new Exception("Can't be a negative integer")

  if (n <= 1)
    return n;

  int s = 0, s1 = 0, s2 = 1;
  for(int i= 2; i<=n; i++) {
    s = s1 + s2;
    s1 = s2;
    s2 = s;            
  }
  return s;
}
0
vic

Ich kann der Versuchung nicht widerstehen, einen linearen iterativen Zeitalgorithmus für Fib mit der exponentiellen rekursiven Zeit zu verknüpfen: Wenn man Jon Bentleys wunderbares kleines Buch über "Writing Efficient Algorithms" liest, glaube ich, dass dies ein einfacher Fall von "Caching" ist: k) berechnet wird, speichern Sie es im Array FibCached [k]. Wenn Fib (j) aufgerufen wird, prüfen Sie zuerst, ob es in FibCached [j] zwischengespeichert ist. wenn ja, den Wert zurückgeben; wenn nicht, rekursion verwenden. (Schauen Sie sich jetzt den Anrufbaum an ...)

0
Alex B.