Mastertheorem
-
Kennt jemand ein reales Beispiel für die anderen Fälle des Mastertheorems? Ich komme immer nur auf den ersten Fall.
T(n) = a*T(n/b) + f(n)
Bei der binären Suche wird die Formel zu:
T(n) = 1*T(n/2) + cKennt jemand einen echten Fall wo f(n) nicht konstant ist?
-
Klar, jede Menge! Zum Beispiel diverse Algorithmen für planare Graphen, die auf dem Planar-Separator-Theorem basieren: Matchings, Mixed-Max-Cut, ...
Quicksort ist auch so ein Kandidat. Unter der Annahme, dass Dein Pivotelement immer der Median ist kriegste die Rekurrenz T(n) = 2*T(n/2) + O(n). 2*T(n/2) für die beiden Teile, die rekursiv sortiert werden, O(n) für's partitionieren.
-
Vielen Dank Jester
