Komplexität des rekursiven Fibonacci-Algorithmus

13

Verwenden des folgenden rekursiven Fibonacci-Algorithmus:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

Wenn ich die Zahl 5 eingebe, um fib (5) zu finden, weiß ich, dass dies 5 ausgibt, aber wie überprüfe ich die Komplexität dieses Algorithmus? Wie berechne ich die Schritte?

algorithms time-complexity recursion Joker
quelle
1
cs.berkeley.edu/~vazirani/algorithms/chap0.pdf
avi
Ich suchte das Gleiche und stolperte über dieses Video von MyCodeSchool. Ich empfehle, es auszuprobieren .
Snbk97

Antworten:

23

In den meisten Fällen können Sie die rekursiven Algorithmen mithilfe von rekursiven Gleichungen darstellen. In diesem Fall lautet die rekursive Gleichung für diesen Algorithmus . Dann können Sie die geschlossene Form der Gleichung mithilfe der Substitutionsmethode oder der Expansionsmethode (oder einer anderen Methode zur Lösung von Wiederholungen) finden. In diesem Fall erhalten Sie T ( n ) = Θ ( ϕ n ) , wobei ϕT(n)=T(n−1)+T(n−2)+Θ(1)T(n)=Θ(ϕn)ϕist der goldene Schnitt ( ).ϕ=(1+5)2

Wenn Sie mehr über das Lösen von Wiederholungen erfahren möchten, empfehlen wir Ihnen dringend, Kapitel 4 der Einführung in Algorithmen zu lesen .

ees_cu
quelle
0

alternativ zu wiederkehrenden beziehungen / mathematischen analysen (aber nicht als ersatz ) besteht eine einfache empirische übung, die anscheinend nicht sehr oft in klassen unterrichtet wird, aber sehr informativ ist, darin, die anzahl der ausführungen der funktion zu zählen und dann die zählung für einen bereich grafisch darzustellen von kleinen n Eingaben und dann Kurve passen das Ergebnis. Die Ergebnisse stimmen im Allgemeinen gut mit dem theoretischen mathematischen Ansatz überein.

Ein gutes Begleitmaterial für diese Übung finden Sie im kostenlosen Online-Kapitel 3, Laufzeit von Algorithmen / Grundlagen der Informatik , Ullman

vzn
quelle
1) Das Plotten ersetzt in keiner Weise die formale Analyse. Es ist leicht zu täuschen. 2) Ich denke, dass Sie die Quelle, die Sie zitieren, falsch darstellen. Sie erwähnen das Plotten, aber nicht , um die "Komplexität" zu bestimmen. 3) FWIW, ich bin mit dem Ansatz nicht einverstanden und er wird so verwendet, wie Ullman ihn präsentiert, aber das ist nicht deine Schuld.
Raphael
1
Die Antwort beginnt im Wesentlichen mit Ihrem Haftungsausschluss: Das Zeichnen ist kein Ersatz für die mathematische Analyse . Das Zeichnen ist eine wissenschaftliche Methode, und zu sagen / zu beobachten, dass es manchmal täuscht, bedeutet, statistische Aspekte von Daten zu lernen / hervorzurufen, was ein weiterer wichtiger Aspekt der wissenschaftlichen Analyse ist . denke , es ist zu sagen , ist „leicht täuschen“ ziemlich dramatisch ist, gibt es „pathologisch“ Fälle , in denen es nicht , aber sie in der Regel „erfunden“ werden ... war die Frage nach der Komplexität des Algorithmus zu untersuchen und empirische Analyse ist ein wichtiger Aspekt / Winkel auf, und natürlich nicht die einzige Winkel etc ...
vzn
0

Das Ergebnis von fib (n) ist die Summe aller rekursiven Aufrufe, die 1 zurückgegeben haben. Daher gibt es genau fib (n) rekursive Aufrufe, die fib (1) auswerten. Die Ausführungszeit ist also Ω (fib (n)); Sie müssen zeigen, dass die Aufrufe, die 0 zurückgeben, und die anderen rekursiven Aufrufe nicht wesentlich dazu beitragen.

Dieselbe Argumentation würde für jede rekursiv definierte Funktion gelten, die entweder 1 oder 0 oder das Ergebnis eines anderen rekursiven Aufrufs zurückgibt.

gnasher729
quelle
Ω
Fühlen Sie sich frei, die Antwort zu bearbeiten, wenn Sie stark davon überzeugt sind.
gnasher729
0

T(n)=T(n-1)+T(n-2) T(n)>2T(n-2)T(n-1)>T(n-2)T(n)=Ω(cn)

Wabbit
quelle