Sortier-Algorithmen Laufzeit < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:24 Mo 26.04.2010 | | Autor: | maxm |
| Aufgabe | | Geben Sie für folgende Sortier-Algorithmen die Laufzeit im durchschnittlichen und schlechtesten Fall(average und worst case) in Abhängigkeit von der Länge n der Eingabesequenz an. Welche Laufzeit haben die Algorithmen bei einer bereits sortierten Eingabesequenz der Länge n? (Bei QuickSort wählen Sie als Pivotelement jeweils das mittlere Elemnt). |
Hallo,
ich habe die Aufgabe schon gelöst und bitte euch, sie mir gegebenfalls zu korrigieren.
average case worst case sortierte Eingabesequenz
InsertionSort Theta( [mm] n^{2} [/mm] ) [mm] O(n^{2}) [/mm] O(n)
MergeSort Theta(n*log(n)) O(n*log(n)) O(n*log(n))
QuickSort Theta(n*log(n)) Theta( [mm] n^{2} [/mm] ) O( [mm] n^{2} [/mm] )
Vielen Dank!
P.S.: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mo 26.04.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
