Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Vergleich Insertion-Sort & Merge-Sort (http://www.informatikerboard.de/board/thread.php?threadid=2913)

Geschrieben von Shizmo am 11.03.2016 um 14:08:

  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 [latex]\mathcal{O}(n)[/latex] und die Worst-Case Laufzeit [latex]\mathcal{O}(n^2)[/latex]

Merge-Sort hat eine konstate Laufzeit von [latex]\mathcal{O}(n \cdot log(n))[/latex].

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... verwirrt


Geschrieben von eulerscheZahl am 11.03.2016 um 14:26:

 

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.


Geschrieben von Shizmo am 11.03.2016 um 14:29:

 

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. Zunge raus


Geschrieben von eulerscheZahl am 11.03.2016 um 14:32:

 

Ich glaube du hast den Teil falschverstanden:
MergeSort bestcase = MergeSort worstcase
Das sollst du begründen.


Geschrieben von Shizmo am 11.03.2016 um 14:35:

 

Oh man Zunge raus Zunge raus
Manchmal bin ich echt richtig doof.

Vielen Dank großes Grinsen großes Grinsen


Forensoftware: Burning Board, entwickelt von WoltLab GmbH