Warum hat insertionsort keine lineare Laufzeit und eine Laufzeit von n*logn?
Dieser Algorithmus läuft ja immer linear, warum insertionsort nicht, der ja auch eigentlich nur Vergleiche vollzieht?:
Lösung n-1 vergleiche überall,
2 Antworten
Weil die Summe über n nunmal in O(n^2) liegt.
P.S.: Der hier gezeigte Algo ist das Auffinden des Minimums, das ist ein linearer Scan bei nicht sortierter Eingabe.
Verauche selbst ein Beispiel zu finden, wo insertion sort am schlechtesten abschneidet. Schließe daraus, dass insertion sort im worst case nicht linear sein kann.
Außerdem ist es bewiesen, dass der Worstcase (und der Averagecase) von einem Vergleichsbasierten Sortieralgorithmus NICHT besser als n*Log(n) sein kann.
Ist Quicksort nicht z. B. auch ein Sortieralgorithmus, aber mit Worstcase von n^2? Müsste der nicht auch nlog(n) haben?
Okay, das habe ich kapiert, aber das Beispiel was ich da habe, die Aufgabe 3.1 ist doch auch vergleichsbasierent und hat eine Laufzeit von n-1? Das doch auch linear?