samedi 30 mai 2015

Komplexität Fibonacci

Posted on 15:55 by verona
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

Java Code:


    

  1. 

     
    

    2. 

  2. 

    public static void main(String[] args) {
    

    3. 

  3. 

    test(50);
    

    4. 

  4. 

    }
    

    5. 

  5. 

     
    

    6. 

  6. 

    public static void test(int n)
    

    7. 

  7. 

    {
    

    8. 

  8. 

    long before = System.nanoTime();
    

    9. 

  9. 

    long fib =fib_it(n);
    

    10. 

  10. 

    long after = System.nanoTime();
    

    11. 

  11. 

    System.out.println("Iterativ "+fib+" Zeit: "+((double)after-before)/1000000+" Sekunden");
    

    12. 

  12. 

    //
    

    13. 

  13. 

    System.out.println();
    

    14. 

  14. 

    //
    

    15. 

  15. 

    before = System.nanoTime();
    

    16. 

  16. 

    fib =fib_it(n);
    

    17. 

  17. 

    after = System.nanoTime();
    

    18. 

  18. 

    System.out.println("Rekursiv "+fib+" Zeit: "+((double)after-before)/1000000+" Sekunden");
    

    19. 

  19. 

    //
    

    20. 

  20. 

    System.out.println();
    

    21. 

  21. 

    //
    

    22. 

  22. 

    before = System.nanoTime();
    

    23. 

  23. 

    fib =fib_tail(n);
    

    24. 

  24. 

    after = System.nanoTime();
    

    25. 

  25. 

    System.out.println("Endrekursiv "+fib+" Zeit: "+((double)after-before)/1000000+" Sekunden");
    

    26. 

  26. 

    }
    

    27. 

  27. 

     
    

    28. 

  28. 

    public static long fib_it(int n)
    

    29. 

  29. 

    {
    

    30. 

  30. 

    long tmp0 = 1;
    

    31. 

  31. 

    long tmp1 = 1;
    

    32. 

  32. 

    if(n == 1 || n == 0) return 1;
    

    33. 

  33. 

    else{
    

    34. 

  34. 

    for(int i = 1; i<n; i++)
    

    35. 

  35. 

    {
    

    36. 

  36. 

    long help = tmp1 + tmp0;
    

    37. 

  37. 

    tmp0 = tmp1;
    

    38. 

  38. 

    tmp1 = help;
    

    39. 

  39. 

    }
    

    40. 

  40. 

    return tmp0;
    

    41. 

  41. 

    }
    

    42. 

  42. 

    }
    

    43. 

  43. 

     
    

    44. 

  44. 

     
    

    45. 

  45. 

    public static long fib_rec(long n)
    

    46. 

  46. 

    {
    

    47. 

  47. 

    if(n == 1) return 1;
    

    48. 

  48. 

    else return fib_rec(n-1)+fib_rec(n-2);
    

    49. 

  49. 

    }
    

    50. 

  50. 

     
    

    51. 

  51. 

    public static long fib_tail(int n)
    

    52. 

  52. 

    {
    

    53. 

  53. 

    if(n == 1 || n == 0) return 1;
    

    54. 

  54. 

    return _fib_tail(n, 0, 1, 0);
    

    55. 

  55. 

    }
    

    56. 

  56. 

     
    

    57. 

  57. 

    public static long _fib_tail(int n,long decN,long decdecN, long acc)
    

    58. 

  58. 

    {
    

    59. 

  59. 

    if(n == 1 || n == 0)return acc;
    

    60. 

  60. 

    else{
    

    61. 

  61. 

    return _fib_tail(n-1, decdecN, decN+decdecN, decN+decdecN);
    

    62. 

  62. 

    }
    

    63. 

  63. 

    }
    

    64. 












Komplexität Fibonacci














Categories: 















0
commentaires:
        
















Enregistrer un commentaire




















        

      









Inscription à :
Publier les commentaires (Atom)