Eine Fibonacci-Serie
Ich habe Probleme mit der Zeit- und Komplexitätsanalyse. Ich habe eine Fibonacci-Serie rekursiv gemacht. Ich denke es ist O (n 2 ) . Können Sie die Zeitanalyse herausfinden? Wenn möglich, könnten Sie es näher erläutern?
#include<iostream>
using namespace std;
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
int main()
{
int n;
cout<<"Enter the number:"<<endl;
cin>>n;
fibonacci(n,0,1);
return 0;
}
Antworten
Ich bin mir nicht sicher, ob eine der Antworten die Komplexität wirklich angesprochen hat. Ich werde das tun, indem ich Ihren Algorithmus in einen einfacheren umwandle, ohne die zeitliche Komplexität zu ändern. Dies beweist sowohl die zeitliche Komplexität als auch eine Version des Algorithmus, die möglicherweise leichter zu lesen und zu überlegen ist.
Beginnen wir mit Ihrer Lösung
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
Das else ifTeil wird nicht wirklich benötigt, also lassen Sie uns das löschen und auch die überflüssigen returnBefehle loswerden . [In den Kommentaren wird diskutiert, warum dieser Schritt nicht ganz so unschuldig ist, wie es scheint.]
void fibonacci(int n,int n1,int n2)
{
if(n==0) {
cout<<endl<<n1; }
else {
fibonacci(n-1,n2,n1+n2); }
}
Umkehren der if. Außerdem werde ich eines davon returnzurücksetzen und den Druck aus dem elseTeil herausnehmen.
void fibonacci(int n,int n1,int n2)
{
if(n!=0) {
fibonacci(n-1,n2,n1+n2);
return ; }
cout<<endl<<n1;
}
Wenden Sie die Endrekursionsoptimierung an, dh ersetzen Sie den rekursiven Aufruf und die folgende Rückgabe durch eine Neuzuweisung der Parameter und einen Sprung zum Anfang des Unterprogramms. Dieser Schritt ändert die Raumkomplexität *, jedoch nicht die Zeitkomplexität.
void fibonacci(int n,int n1,int n2)
{
start:
if(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ;
goto start ; }
out<<endl<<n1;
}
Verwenden Sie eine Schleife anstelle von a goto.
void fibonacci(int n,int n1,int n2)
{
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
Sie brauchen die Parameter nicht wirklich, um Parameter zu sein. Ich würde wahrscheinlich das Unterprogramm dokumentieren, damit klar ist, was es tut. Und ich würde die while-Schleife mit einer Invariante dokumentieren, damit klarer wird, wie es funktioniert.
void fibonacci(int n)
// Precondition: n >= 0
// Postcondition: the value of fib(n) has been printed to standard out
// preceded by an end of line.
{
int n1 = 0 ;
int n2 = 1 ;
// Let n0 be the original value if n.
// invariant n1 == fib( n0-n ) and n1 == fib(n0-n+1)
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
(Und ändern Sie natürlich auch den Ort, an dem es heißt.)
An diesem Punkt ist klar (ich denke), dass der Algorithmus O (n) ist. Keine der Transformationen ändert die Zeitkomplexität, daher ist die Zeitkomplexität des Originals auch O (n).
(*) Das heißt, die Raumkomplexität wird von O (n) in O (1) geändert, es sei denn, Ihr Compiler führt eine Tail-Rekursionsoptimierung durch. Wenn dies der Fall ist, war die Raumkomplexität von Anfang an O (1).
Über using namespace std
Sie sollten versuchen, diese Aussage zu vermeiden, da sie als schlechte Praxis angesehen wird . Es ist am besten, es zu vermeiden, wann immer Sie können. Hier ist ein einfaches Beispiel warum.
#include <iostream>
#inlcude <list>
using namespace std;
class list // uh-hoh, list is already defined, or is that std::list?
{
...
};
Ein weiteres Problem besteht darin, dass Sie, wenn Sie dies in einer der Header-Dateien in Ihrem Projekt haben, gezwungen sind, dies in jeder Datei zu verwenden, in die Sie den Header aufgenommen haben.
Warum wird die Verwendung des Namespace std als schlechte Praxis angesehen?
Vorlagen-Metaprogrammierung
Dadurch wird die Berechnung von der Laufzeit zur Kompilierungszeit verschoben . Das Kompilieren Ihres Programms wird etwas länger dauern, aber die Komplexität wird es sein O(1). Es verwendet Vorlagen in C ++ , um den Compiler zur Berechnung des Werts zu zwingen.
Dies ist eine weitere Option, um dieses Problem anzugehen, und der schnellste Weg, da hierdurch die Berechnung zur Kompilierungszeit verschoben wird .
Der Nachteil ist jedoch, dass Sie keine Werte verwenden können, die zur Kompilierungszeit nicht bekannt sind. Beispielsweise könnten Sie den Wert für 5etwas finden, das der Benutzer jedoch nicht eingibt, oder beispielsweise eine generierte Zufallszahl.
#include<iostream>
template <unsigned N>
struct Fibonacci
{
enum : uint64_t
{
value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
};
};
template <>
struct Fibonacci<1>
{
enum
{
value = 1
};
};
template <>
struct Fibonacci<0>
{
enum
{
value = 0
};
};
int main()
{
std::cout << Fibonacci<20>::value;
}
Diese Methode ist die schnellste, funktioniert jedoch nur, wenn Ihre Zahlen konstant sind.
Vorlagen-Metaprogrammierung in C ++
Ersetzen Sie die Rekursion durch Iteration
Obwohl Rekursion Ihren Code ein wenig sauberer macht, läuft Rekursion fast immer langsamer , ist dies, weil für jeden Anruf es Zuweisung eines neuen Stapelrahmen benötigt
Aufgrund der Tatsache , dass der Raum in dem Stapel ist endlich , es gibt eine Grenze, wie viele rekursiven Aufrufe ist Sie können machen, bevor C ++ Ihnen gibt 0xC00000FD. Was Stapelüberlauf ist
Mit ein paar weiteren Codezeilen können Sie die Rekursion durch dieses Szenario ersetzen und es ohne dieses Problem viel schneller machen.
Dies bedeutet nicht, dass Sie keine Rekursion verwenden sollten. Einige Algorithmen benötigen eine Rekursion. Wenn Sie sie jedoch durch Iteration ersetzen können , lohnt es sich.
Hier ist es mit Iteration.
uint64_t fibonacci(int n)
{
uint64_t n1 = 0,n2 = 1,n3 = 1;
if (n == 1 || n == 0) return 0;
else if(n == 2) return 1;
for (int i = 2;i < n;++i)
{
n3 = n1 + n2;
n1 = n2;
n2 = n3;
}
return n3;
}
'\n' Über std::endl
'\n'und std::endlwird sowohl erreichen Ihre Aufgabe, aber std::endlruft std::flushjedes Mal , und spült den Strom, deshalb wird es langsamer sein, als nur Drucken'\n'
Vergleich zwischen std :: endl und '\ n'
Der naheliegendste Weg, um fib zu schreiben:
int fib(int n)
{
if (n < 2) // 0 or 1
{
return 1;
}
return fib(n-1) + fib(n-2);
}
Sie können sehen, dass es explodiert, weil Sie für jeden Aufruf von fib () 2 nachfolgende Anrufe erhalten, die beide 2 Anrufe erhalten, wobei alle 2 Anrufe usw. erhalten.
Level Calls Calls This Level Total Calls
Level n 1 1 1
Level n-1 1 1 2 3
Level n-2 1 1 1 1 4 7
Level n-3 1 1 1 1 1 1 1 1 8 15
Die Komplexität von Fib ist also Fib !!!!!
Genauer gesagt ist Complecity nur O(2Fib(n)-1)
das Entfernen von KonstantenO(Fib(n))
Schreiben wir einen Code, um dies zu überprüfen:
int fibComplexity(int n)
{
// has the same properties of fib.
// but returns the number of calls rather than the value.
if (n < 2)
{
return 1; // You called this function once.
}
return 1 // the call to this function.
+ fibComplexity(n-1) // Count of calls in this tree
+ fibComplexity(n-2) // Count of calls in this tree.
}
Wenn wir das tun:
int main()
{
for(int loop = 2; loop < 15; ++loop)
{
std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
}
}
Erzeugt: (Formatierung hinzugefügt)
n F O
2 2 3
3 3 5
4 5 9
5 8 15
6 13 25
7 21 41
8 34 67
9 55 109
10 89 177
11 144 287
12 233 465
13 377 753
14 610 1219 O = 2f-1
In jedem Codierungskurs werden Sie dann aufgefordert, eine lineare Lösung zu erstellen.
Was Sie oben präsentieren, ist eine rekursive (aber lineare Lösung). Die meisten Leute hätten sich für eine schleifenbasierte lineare Lösung entschieden (aber es gibt keinen Unterschied). Die Komplexität ist genau gleich.
Was Sie getan haben, ist rekursiv die Funktion aufzurufen, die Dinge addiert, während Sie gehen. Jeder Anruf führt genau einen zusätzlichen Anruf aus, jedoch nur bis zu einer Tiefe von n. Dann kehrt es zurück.
Sie haben also Komplexität von O(n).
Aber Sie können noch einen Schritt weiter gehen. Der Fib-Algorithmus kann leicht als implementiert werden O(1).
Dies liegt daran, dass fib schnell die Größe einer ganzen Zahl übersteigt (sogar lang lang). Sie können alle gültigen Werte, die in einer Variablen gespeichert werden können, einfach vorberechnen und in ein Array einfügen. Geben Sie dann einfach den Wert zurück, indem Sie das Ergebnis nachschlagen:
int fib(int n) {
static const int fibValue[] = { ... };
if (n < 0 || n > std::size(fibValue)) {
// This is 47 for 32 bit ints
// 93 for 64 bit ints
throw "Result out of range"
}
return fibValue[n];
}
Nur um explizit zu sein: Sie sind \$O(n)\$in der Zeit und \$O(n)\$in Erinnerung. Ich glaube nicht, dass Sie in der Ganzzahlarithmetik (wenn Sie sie tatsächlich berechnen) in der Zeit leicht besser abschneiden können, aber der Speicher könnte \ sein$O(1)\$.
Wie Peter Cordes betont hat , gibt es für die Fibonacci-Sequenz eine " geschlossene Form ". Wenn Sie also ein Gleitkommasystem mit konstanter Zeit und unendlicher Genauigkeit haben, können Sie \ erreichen$O(1)\$. Computer-Gleitkomma kann eine Annäherung erreichen, aber ich denke, Sie werden mit ganzzahliger Mathematik genauere Ergebnisse erzielen.
Wie auch von Peter Cordes hervorgehoben , gibt es eine " Lucas-Sequenzmethode ", die \ kann$O(\log{n})\$ gegebene ganzzahlige Multiplikation und ein gutes Stück mehr Komplexität.
Wenn Sie Ihre Funktion iterativ verwenden, um die Fibonacci-Sequenz zu drucken, lautet Ihr Zeitergebnis \$O(n^2)\$, und das kann in \ gemacht werden$O(n)\$.