Rekursionsgleichung aufstellen |
09.04.2016, 22:57 | Auf diesen Beitrag antworten » | |||||
Shizmo | Rekursionsgleichung aufstellen Hallo, ich soll von einem rekursiven Sortier-Algorithmus die Rekursionsgleichung aufstellen, um dann mit dem Master-Theorem die Komplexitätklasse abschätzen zu können. Der Teil mit dem Master-Theorem ist kein Problem, allerdings weiß ich nicht, wie ich eine Rekursionsgleichung zu einem Algorithmus aufstellen soll. Hier mal der "sehr schlechte" Algorithmus:
Die allgemeine Rekursionsgleichung sieht so aus: LG |
|||||
|
||||||
10.04.2016, 08:51 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Du hast 3 rekursive Aufrufe, also ist a=3. Die Teilprobleme haben jeweils eine Größe von 2/3 des ursprünglichen Problems (so ungefähr). Also ist b=3/2. f(n) ist eine Konstante, weil nur ein Vergleich und evtl. eine Vertauschen durchgeführt wird. Das legt kubische Laufzeit nahe. Hier mal ein Plot mit der Laufzeit (blau - und ja, das ist wirklich so eckig) und x^3/5 (rot). |
|||||
10.04.2016, 10:49 | Auf diesen Beitrag antworten » | |||||
Shizmo | Ah okay, super vielen Dank. Also: Lt. Master-Theorem gilt dann: |
|||||
10.04.2016, 10:53 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Sieht gut aus. |
|||||
Anzeige | ||||||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |