Vergleich Insertion-Sort & Merge-Sort |
| 11.03.2016, 14:08 | Auf diesen Beitrag antworten » | ||
| Shizmo | Vergleich Insertion-Sort & Merge-Sort Hallo, mal eine grundsätzliche Frage zu:
Hmm, die Best-Case Laufzeit von Insertion-Sort ist Merge-Sort hat eine konstate Laufzeit von Also hat mMn Insertion-Sort werde dieselbe Best- noch Worst-Case Laufzeit als Merge-Sort, wie soll ich das dann vergleichen? Oder darf man bei Merge-Sort den log wegstreichen, da ja das lineare n mehr zählt???? Dann hätten sie dieselbe Best-Case Laufzeit... 
|
||
|
|
|||
| 11.03.2016, 14:26 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl |
Auf keinen Fall. Insertion Sort kann schneller als Merge Sort sein, aber auch deutlich langsamer. Das interessante ist der Average Case. Hier ist Insertion Sort bereits quadratisch, also schlechter als Merge Sort. Quicksort kann auch quadratische Laufzeit haben, im Normalfall ist sie aber n*log(n). Da kommt es dann wirklich auf die Konstante an, die bei der O Notation wegfällt. Die ist bei Quicksort vergleichsweise klein, weshalb der Algorithmus häufig verwendet wird. |
||
| 11.03.2016, 14:29 | Auf diesen Beitrag antworten » | ||
| Shizmo | Okay, aber was hat die Aufgabe für einen Sinn? Also es steht ja: "Klären Sie im speziellen, warum Merge-Sort die gleiche Worst- bzw. Best-Case Laufzeit hat." Hat es ja nicht, weder noch. 
|
||
| 11.03.2016, 14:32 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Ich glaube du hast den Teil falschverstanden: MergeSort bestcase = MergeSort worstcase Das sollst du begründen. |
||
| Anzeige | |||
|
|
|||
| 11.03.2016, 14:35 | Auf diesen Beitrag antworten » | ||
| Shizmo | Oh man
Manchmal bin ich echt richtig doof. Vielen Dank 
|
||
|
|
