Komplexität Fibonacci

[InfoStudent114]

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]

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]

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]

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]

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]

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]

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]

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