O-Notationen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Community,
kann mir jemand helfen die Laufzeit von folgendem Code zur Berechnung der Fibonacci Zahlen zu berechnen?
Die for-Schleife in der main Funktion hat eine Laufzeit von O(n). Die for schleife in der der Funktion hat die selbe Laufzeit, abhängig von n. Sonst ist alles O(1).
Wie kann ich nun beide verrechnen, um auf ein Gesamtergebnis zu kommen?
int fibonacci(int n)
{
int prevFib=0;
int cur=1;
if(n==0)
{
return 0;
}
if(n==1)
{
return 1;
}
for(int i=2; i<=n;i++)
{
int new= prev+ cur;
prev= cur;
cur= new;
}
return cur;
}
int main(int argc, char **argv)
{
cout << "Fibonacci-Zahlen:" << endl;
for(int i=0; i<12; i++)
{
cout << "f(" <<i << ") = " << fibonacci(i) << endl;
}
}
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:13 Sa 13.04.2013 | | Autor: | kaju35 |
Hallo TimeforKai,
> int fibonacci(int n)
> {
> int prevFib=0;
> int cur=1;
> if(n==0)
> {
> return 0;
> }
> if(n==1)
> {
> return 1;
> }
> for(int i=2; i<=n;i++)
> {
> int new= prev+ cur;
> prev= cur;
> cur= new;
>
> }
> return cur;
> }
>
Hast Du das in der Form kompiliert bekommen?
Du deklarierst prevFib=0, benutzt aber im weiteren
Verlauf eine Variable namens prev.
Desweiteren ist die Deklaration einer Variable
in einer Schleife gar kein guter Stil.
Abgesehen davon ist die Laufzeit von fibonacci(i)
so weit ich das sehe gleich i. In der Schleife in
main läuft i von 0 bis n, was eine Laufzeit von
0+1+2+3+...+n ergibt. Das ist [mm] $\frac{n\cdot(n+1)}{2}$.
[/mm]
Gruß
Kai
|
|
|
| |
|
Hallo!
Im grunde hat kaju35 schon alles gesagt, und sogar eine sehr genaue Angabe der Laufzeit angegeben. Daher gilt die Frage hiermit erstmal als offiziell beantwortet.
Allerdings gibt man bei der Laufzeit in der O-Notation nur den dominierenden Term an, und das ohne irgendwelche Vorfaktoren. Das heißt, wenn man die Klammer auflöst, kommt man auf [mm] O(n^2) [/mm] . Mit wachsendem n spielt der zusätzliche Term +n kaum eine Rolle mehr.
|
|
|
|
