| Die letzten 5 Beiträge |
| Shizmo |
Oh man 
Manchmal bin ich echt richtig doof.
Vielen Dank 
|
| eulerscheZahl |
Ich glaube du hast den Teil falschverstanden:
MergeSort bestcase = MergeSort worstcase
Das sollst du begründen. |
| 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.
|
| eulerscheZahl |
| 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. |
| Shizmo |
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]](http://www.matheboard.de/latex2png/latex2png.php?\mathcal{O}(n)) und die Worst-Case Laufzeit ![[latex]\mathcal{O}(n^2)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\mathcal{O}(n^2))
Merge-Sort hat eine konstate Laufzeit von ![[latex]\mathcal{O}(n \cdot log(n))[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\mathcal{O}(n \cdot log(n))) .
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... 
|
|
|
