# Komplexität Fibonacci



## InfoStudent114 (31. Mai 2015)

Erstmal guten Abend Leute,

im folgenden eine kleine Frage, die nach ein wenig herumspielen entstanden ist. In Vorlesungen (und auch im Internet) finde ich immer wieder die Komplexität für die Berechnung der Fibonacci Folgen mit O(n) [iterativ] und O(2^n) [rekursiv]
Ist ja auch entsprechend der Funktionen sinnvoll. Hab das ganze jetzt einmal in Java Code Umgesetzt und die Zeit gemessen- jetzt wüsst ich gern, ob mir jemand erklären kann warum die Ergebnisse doch recht auffällig von der zu erwartenden Zeit abweichen. (Zum ersten mal in diesem Forum aktiv- hoffe einfach mal, jetzt keine groben Formfehler begangen zu haben)

Erstmal das Ergebnis der Ausgabe (Eingabe 50)

Iterativ 12586269025 Zeit: 0.009179 Sekunden


Rekursiv 12586269025 Zeit: 0.00378 Sekunden


Endrekursiv 12586269025 Zeit: 0.016739 Sekunden

und im Folgenden noch der Code


```
public static void main(String[] args) {
            test(50);
    }
    
    public static void test(int n)
    {
        long before = System.nanoTime();
        long fib =fib_it(n);
        long after = System.nanoTime();
        System.out.println("Iterativ "+fib+" Zeit: "+((double)after-before)/1000000+" Sekunden");
        //
        System.out.println();
        //
        before = System.nanoTime();
        fib =fib_it(n);
        after = System.nanoTime();
        System.out.println("Rekursiv "+fib+" Zeit: "+((double)after-before)/1000000+" Sekunden");
        //
        System.out.println();
        //
        before = System.nanoTime();
        fib =fib_tail(n);
        after = System.nanoTime();
        System.out.println("Endrekursiv "+fib+" Zeit: "+((double)after-before)/1000000+" Sekunden");
    }
    
    public static long fib_it(int n)
    {
        long tmp0 = 1;
        long tmp1 = 1;
        if(n == 1 || n == 0) return 1;
        else{
            for(int i = 1; i<n; i++)
            {
                long help = tmp1 + tmp0;
                tmp0 = tmp1;
                tmp1 = help;
            }
            return tmp0;
        }
    }


    public static long fib_rec(long n)
    {
        if(n == 1) return 1;
        else return fib_rec(n-1)+fib_rec(n-2);
    }
    
    public static long fib_tail(int n)
    {
        if(n == 1 || n == 0) return 1;
        return _fib_tail(n, 0, 1, 0);
    }
    
    public static long _fib_tail(int n,long decN,long decdecN, long acc)
    {
        if(n == 1 || n == 0)return acc;
        else{
            return _fib_tail(n-1, decdecN, decN+decdecN, decN+decdecN);
        }        
    }
```


----------



## Flown (31. Mai 2015)

Du hast bei deiner Messung ein Copy&Paste Fehler drinnen du rufst bei deiner rekursiven Berechnung die Iterative auf. 

Ob rekursiv oder endrekursiv ist in Java egal, da hier nichts optimiert wird (im Gegensatz zu Scala).

Solche Zeitmessungen sind in Java mit Vorsicht zu genießen, denn Microbenchmarks für Java sind eigentlich nur etwas für Profis.  Aber dazu mehr findest du im Internet.

PS: Deine Zeitberechnung berechnet dir keine Sekunden, sondern Millisekunden.
PPS: Deine rekursive Methode hat eine falsche Abbruchbedingung. Richtig wäre: n <= 2
PPPS: Die tailrecursive Methode kann man kürzer schreiben.


----------



## CSHW89 (1. Jun 2015)

Flown hat ja schon was zu deiner Messmethode gesagt. Allerdings scheinst du eine Beziehung zwischen O(n) und O(2^n) zu erwarten, die so nicht existiert. Du erwartest vermutlich bei sagen wir mal n=5, dass das Verhältnis zwischen beiden Laufzeiten 6.4 ist, da ((2^n) / n) = 32/5 = 6.4.
In Wahrheit kann es aber sogar sein, dass der O(2^n) Algo bei n=5 schneller ist als der O(n) Algo (in diesem Fall vermutlich nicht, aber bei anderen Algos durchaus möglich). Die O-Notation sagt nur folgendes aus: wie schnell die Laufzeit eines Algorithmus steigt bei steigendem n. Über die Laufzeit bei genau einem einzigen n kannst du keine Aussage treffen.
Was du also herausfinden könntest, wäre z.b. dass der O(n) Algo bei n=20 4-mal so schnell ist wie bei n=5, und dass der O(2^n) Algo bei n=20 32768-mal so schnell ist wie bei n=5, da (2^20)/2^5=2^15=32768.
Aber eine Beziehung zwischen Laufzeiten *verschiedener* Algos gibt es nicht!

lg Kevin


----------



## InfoStudent114 (1. Jun 2015)

Erstmal danke für die schnelle Antwort

der Copy und Paste Fehler... *hust* peinlich *hust*

Fehler beseitigt und noch einmal geprüft und auch wenn wohl die Zeitmessung dank der VM mit Vorsicht zu genießen ist, lässt sich mit dem neuen Ergebnis leben

n = 20
Iterativ 6765 Zeit: 0.005939 


Rekursiv 6765 Zeit: 1.442759 


Endrekursiv 6765 Zeit: 0.021059


----------



## DefconDev (7. Jun 2015)

Hallo, ich möchte das Thema noch mal kurz aufgreifen.

Inwiefern kann man dann Algos miteinander vergleichen in ihrer Geschwindigkeit? Ich dachte bisher immer, rekursiv wäre generell langsamer als iterativ.


----------



## stg (7. Jun 2015)

Das ist oft der Fall, aber in der allgemeinen Formulierung schlicht falsch. 

Aber selbst wenn, wieso sollte man dann die Laufzeiten nicht vergleichen können?!


----------



## DefconDev (8. Jun 2015)

stg hat gesagt.:


> Das ist oft der Fall, aber in der allgemeinen Formulierung schlicht falsch.
> 
> Aber selbst wenn, wieso sollte man dann die Laufzeiten nicht vergleichen können?!



Und wie wäre es richtig formuliert? 

Wenn ich den Beitrag von  CSHW89 richtig verstanden habe, kann man die Algos in keiner Beziehung zueinander stellen. Sondern nur die Zeit zwischen den Schritten.


----------



## CSHW89 (8. Jun 2015)

Vermutlich habe ich meinen Beitrag etwas zu totalitär geschrieben. Es ging hauptsächlich um die O-Notation, dass man zwei Algorithmen mit Laufzeiten z.b. O(n) bzw. O(2^n) nicht anhand einer Stichprobe vergleichen kann, sondern nur deren Verlauf bei steigendender Eingabelänge n. Natürlich kannst du testen, ob Algorithmus A bei einer bestimmten Eingabe schneller ist als Algorithmus B. Aber bei einer anderen Eingabe kann es wieder ganz anders aussehen.

lg Kevin


----------

