Previous: Heapsort
Up: Sortieren
Next: Bucket Sort
Entscheidungsbaum zur Sortierung von 3 Elementen:
gegeben
Der Entscheidungsbaum zur Sortierung von
Elementen
hat
! Blätter.
![$\Rightarrow$](img105.gif)
- Ein binärer Baum mit
Blättern hat mindestens
die Höhe
.
![$\Rightarrow$](img105.gif)
- Jeder Sortieralgorithmus, der auf Vergleichen beruht, hat als Laufzeit
mindestens
. Dies ist eine untere Schranke.
Previous: Heapsort
Up: Sortieren
Next: Bucket Sort