|
Registriert seit: 4. Sep 2003
Ort: Hemer
104 Beiträge
Turbo Delphi für Win32
|
Re: Komplexität eines Algorithmus abschätzen
9. Dez 2004, 21:27
Radix Sort sortiert mit linearem Aufwand. Allerdings nicht durch Vertauschen oder Vergleichen, sondern die Position eines Elementes wird direkt errechnet, was ja zumindest bei Zahlen nicht weiter schwer aber auch nicht wirklich nützlich ist.
Beim Sortieren durch Vergleichen und Vertauschen ohne zusätzlichen Speicher kann man glaube ich auch Beweisen, dass es keinen schnelleren Algorithmus geben kann. Ich glaube der Beweis geht so, dass man für jedes Element einen binären Entscheidungsbaum aufstellt, der dann natürlich eine Tiefe von log(n), also log(n) Entscheidungen, enthält und das ganze dann n Mal durchgeführt wird.
|