Vergleich Insertion-Sort & Merge-Sort |
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Vergleich Insertion-Sort & Merge-Sort |
|
Hallo, mal eine grundsätzliche Frage zu:
Zitat: |
Vergleichen Sie Insertion-Sort und Merge-Sort hinsichtlich der Worst-Case bzw. Best-Case Laufzeiten. Klären Sie im speziellen, warum Merge-Sort die gleiche Worst- bzw. Best-Case Laufzeit hat. |
Hmm, die Best-Case Laufzeit von Insertion-Sort ist und die Worst-Case Laufzeit
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:08 |
|
|
|
Zitat: |
Oder darf man bei Merge-Sort den log wegstreichen, da ja das lineare n mehr zählt? |
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
11.03.2016 14:26 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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:29 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Oh man
Manchmal bin ich echt richtig doof.
Vielen Dank
|
|
11.03.2016 14:35 |
|
|
|