Laufzeit von Quicksort/Mergesort --> nlogn

Math55

Mitglied
hallo, kann mir mal jemand erklären, wie die laufzeit von O(nlogn) zustande kommt? ich kann mir die algorithmen so oft anaschauen, wie ich will, ich schnalls nicht :-|. es wird zwar überall erklärt, wie die funktionieren, aber nirgends, wie dann die laufzeit zustande kommt....

vielen dank
 

wookenny

Erfahrenes Mitglied
Zu MergeSort kann ich dir nix genaues sagen.
Ach doch....wir hatten da so Sätze drüber (Aufteilngs und beschleunigungssatz).
Der sagt was über die Laufzeit von so Divide & Conquer Algos.
Damit folgt die Laufzeit direkt.

QuickSort aber doch: im WorstCase hat dieser Algo eine Laufzeit von O(n²).
Nur im AverageCase erreicht er O(n log n).

Das habe ich in dem meiner Vordiplomsprüfung "Computerorientierte Mathematik" dem Prof. bewiesen.
Am besten liest du dir den Beweis mal nach.
hier ein schönes Skript meines damaligen Profs und jetztigen Chefs Klick