4. Rekursiver Algorithmus

Rekursiver Algorithmus

  • C

    Der rekursive Algorithmus soll untersucht werden: Angabe

    Berechnet werden soll die Laufzeit des Algorithmus in Abhängigkeit von n für die Fälle:

    a.) n = 2^m
    b.) n = 2^m -1

    Die Lösungen dazu sind wie folgt:
    Lösung von a.)
    Lösung von a.) vereinfachte Form

    Dabei stellt sich nun die Frage wie man darauf kommt ?
    Hat das damit zu tun, dass 2^m = 2*2^(m-1) ist und die Multiplikation von dem *2 kommt ?
    Was bedeutet in diesem Zusammenhang f(1) und was das +d ganz hinten ?

    Ach ja und noch eine Frage wie kommt man durch den log2 von der ersten Form auf die zweite ?
    _____

    Lösung von b.)
    Ich hoffe, dass ich das selber rausfinde wenn mir jemand a.) erklären kann, nur so viel, was ist das +e ganz hinten ?

    Vielen Dank 🙂

    0
  • ?

    Hallo.

    Die Laufzeit hängt von der Implementierung ab.

    Fall n=2^m :

    Naiver (schlechter) Ansatz:
    f(n) = f(2^m) = 2*f(2^(m-1))
    Hier wurde verwendet, dass sich das Problem 2^m zu berechnen mit gegebener Rekursion darauf zurückführen lässt, zwei Probleme der Form 2^(m-1) zu lösen.
    Das setzt man nun einfach fort

    2*f(2^(m-1)) = 2^2 * f(2^(m-2)) = 2^3 * f(2^(m-3)) = ... = 2^m * f(2^0) = 2^m + d = n + d = O(n)
    Dabei sind d die Kosten 2^0 zu berechnen. Die sind natürlich konstant.

    Die Laufzeit ist also in diesem Fall linear und somit unbrauchbar.

    Nun zur Musterlösung.
    f(n) = f(2^m) = c + f(2^(m-1))
    Wir können natürlich wieder das Problem 2^m auf 2^(m-1) zurückführen. Aber statt beide explizit nach gegebener Formel zu berechnen wird es nur einmal gemacht und das Ergebnis dann quadriert. Die Kosten für diese Multiplikation sind Konstant und mit c bezeichnet. Das ist genau genommen falsch, weil eine Multiplikation keine konstante Laufzeit hat aber das wird meist vernachlässigt. Man sieht es i.d.R. als elementare Rechenoperation an, die keine von der Eingabe abhängige Zeit verbraucht.

    So ergibt siche weiter
    c + f(2^(m-1)) = 2c + f(2^(m-2)) = 3c + f(2^(m-3)) = ... = mc + f(2^0) = mc + d = log_2(n)*c + d = O(log n)

    wobei d wieder die Kosten für 2^0 sind.
    Dass in der Lösung mc + f(1) + d ist imho falsch. Das f(1) gehört da nicht mehr hin. Ganz abgesehen davon ist das d in beiden Fällen überflüssig weil es eine zu detaillierte Analyse ist. Wichtig ist, dass die erste "Implementierung" lineare, die zweite nur logarithmische Laufzeit hat.

    MfG

    0
  • ?

    Hi,

    mit e wird in der Mathematik im Allgemeinen die Eulersche Zahl 2.7182818284590451 bezeichnet.

    Gruß

    Dookie

    0
  • ?

    @Dookie
    Hast du dir die Aufgabe überhaupt angesehen? Dieses "e" hat hier garnichts mit der Eulerschen Zahl zu tun.

    @CrazyOwl
    Und kriegst du den Rest alleine hin?

    0
  • C

    Danke für die ausführliche Erklärung. Der Rest sollte alleine gehen, sonst meld ich mich nochmal.
    THX jedenfalls. 🙂

    0
Anmelden zum Antworten