Quicksort mit Median als Pivotelement |
| 09.05.2018, 16:54 | NicoBe | Auf diesen Beitrag antworten » |
| Quicksort mit Median als Pivotelement es geht darum, die worst case Laufzeit von Quicksort zu ermitteln, wenn als Pivotelement der Median gewählt wird, welcher dann an Stelle A[0] gestellt wird und von da an der Algo ganz normal läuft. Der normale Quicksort hat ja eine Laufzeit von O(n^2). Um die Änderung zu zeigen, möchte ich zuerst eine Rekurrenzgleichung aufstellen, die die Laufzeit beschreibt. Dabei würde ich für den Fall n>=2 einfach den Term c_1 * n + c_2 für die Berechnung des Medians an die ursprüngliche Rekurrenzgleichung von Quicksort anhängen. Hat jemand dazu noch Ideen oder Ratschläge zu weitermachen? LG, Nico |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
