Ob die iterativen und rekursiven Versionen von zwei Algorithmen dieselbe Komplexität haben? Sagen Sie zum Beispiel die iterativen und rekursiven Versionen der Fibonacci-Reihe.
Die Antwort hängt stark von Ihrer Implementierung ab. Für das Beispiel, das Sie angegeben haben, gibt es mehrere mögliche Lösungen und ich würde sagen, dass der naive Weg, eine Lösung zu implementieren, eine bessere Komplexität aufweist, wenn iterativ implementiert wird. Hier sind die zwei Implementierungen:
%Vor% In beiden Implementierungen nahm ich eine korrekte Eingabe an, dh n & gt; = 1. Der erste Code ist viel länger, aber seine Komplexität ist O (n), dh linear, während die zweite Implementierung kürzer ist, aber exponentielle Komplexität O (fib (n )) = O (φ ^ n) ( φ = (1+√5)/2 ) und ist somit viel langsamer.
Man kann die rekursive Version verbessern, indem man Memoization einführt (d. H. Sich an die Rückgabewerte der Funktion erinnert, die Sie bereits berechnet haben). Dies geschieht normalerweise, indem ein Array eingeführt wird, in dem Sie die Werte speichern. Hier ist ein Beispiel:
Hier ist die Komplexität des rekursiven Algorithmus genauso linear wie die iterative Lösung. Die Lösung, die ich oben vorgestellt habe, ist der Top-Down-Ansatz für die dynamische Programmierung Ihres Problems. Der Bottom-up-Ansatz wird zu etwas führen, das der von mir als iterativ vorgestellten Lösung sehr ähnlich ist. Es gibt viele Artikel über dynamische Programmierung, einschließlich in wikipedia
Abhängig von den Problemen, die ich nach meiner Erfahrung getroffen habe, sind manche mit einem Bottom-up-Ansatz (iterative Lösung) viel schwieriger zu lösen, während andere mit einem Top-down-Ansatz schwer zu lösen sind. Die Theorie besagt jedoch, dass jedes Problem, das eine iterative Lösung hat, mit derselben Rechenkomplexität rekursiv ist (und umgekehrt).
Ich hoffe, diese Antwort hilft.
Der spezielle rekursive Algorithmus zur Berechnung von Fibanocci-Reihen ist weniger effizient. Betrachten Sie die folgende Situation, in der Sie fib (4) durch den rekursiven Algorithmus finden
%Vor%Wenn der obige Algorithmus nun für n = 4 ausgeführt wird
%Vor%Es ist ein Baum. Es besagt, dass Sie zur Berechnung von fib (4) fib (3) und fib (2) berechnen müssen usw.
Beachten Sie, dass sogar für einen kleinen Wert von 4 fib (2) zweimal berechnet wird und fib (1) dreimal berechnet wird. Diese Anzahl von Additionen wächst für große Zahlen.
Es gibt eine Vermutung, dass die Anzahl der für die Berechnung von fib (n) erforderlichen Additionen
ist %Vor%Diese Duplizierung ist also der Grund für die reduzierte Leistung in diesem speziellen Algorithmus.
Der iterative Algorithmus für Fibonacci-Reihen ist wesentlich schneller, da er nicht die redundanten Dinge berechnet.
Es kann jedoch nicht für alle Algorithmen der gleiche Fall sein.
Wenn Sie einen rekursiven Algorithmus verwenden, können Sie ihn in iterativ konvertieren, indem Sie alle lokalen Variablen der Funktion in einem Array speichern und Stack auf Heap effektiv simulieren. Wenn dies so gemacht wird, gibt es keinen Unterschied zwischen iterativ und rekursiv.
Beachten Sie, dass es (mindestens) zwei rekursive Fibonacci-Algorithmen gibt. Um genau zu sein, müssen Sie also angeben, über welchen rekursiven Algorithmus Sie sprechen.
Ja, wenn Sie genau dieselben Ideen verwenden, die dem Algorithmus zugrunde liegen, ist das egal. Die Rekursion ist jedoch oft einfach in Bezug auf die Iteration zu verwenden. Zum Beispiel ist das Schreiben einer rekursiven Version der Türme von Hanoi ziemlich einfach. Das Transformieren der rekursiven Version in eine entsprechende iterative Version ist schwierig und fehleranfällig, obwohl dies möglich ist. Tatsächlich gibt es einen Satz, der besagt, dass jeder rekursive Algorithmus in einen äquivalenten iterativen Algorithmus umgewandelt werden kann (dazu muss die Rekursion iterativ nachgeahmt werden, indem eine oder mehrere Stapel-Datenstrukturen verwendet werden, um an rekursive Aufrufe übergebene Parameter zu halten).
Ja, jeder iterative Algorithmus kann in eine rekursive Version umgewandelt werden und umgekehrt. Eine Möglichkeit besteht darin, Fortsetzungen und die andere durch die Implementierung einer Stapelstruktur zu passieren. Dies geschieht ohne Erhöhung der zeitlichen Komplexität.
Wenn Sie die Tail-Rekursion optimieren können, kann jeder iterative Algorithmus in rekursive umgewandelt werden, ohne die Komplexität des asymptotischen Speichers zu erhöhen.
Tags und Links algorithm time-complexity complexity-theory