Laufzeit von Quicksort/Mergesort --> nlogn

M

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
 
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
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück