Quicksort Gleichverteilung |
| 13.05.2018, 18:59 | NicoBe | Auf diesen Beitrag antworten » |
| Quicksort Gleichverteilung ich habe folgende Aussage zu beweisen (es geht um den Algorithmus Quicksort): Sei k das Pivotelement. Nach dem Aufteilen ergeben sich demnach Teilfelder der Länge k-1 und n-1, wobei n die Gesamtlänge des Feldes ist. Aussage: mit einer Wahrscheinlichkeit von 1/(k-1)! bzw. 1/(n-k)! sind die Teilfelder gleichverteilt. Mir fehlt für diese Aussage komplett der Ansatz, hat jemand einen Vorschlag? LG, Nico |
||
|
|
