Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Vergleich Insertion-Sort & Merge-Sort

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Vergleich Insertion-Sort & Merge-Sort

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Vergleich Insertion-Sort & Merge-Sort

Zitatantwort auf diesen Beitrag erstellen

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

11.03.2016 14:08

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

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

11.03.2016 14:29

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

11.03.2016 14:32

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Oh man

Manchmal bin ich echt richtig doof.

Vielen Dank großes Grinsen

11.03.2016 14:35

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Vergleich Insertion-Sort & Merge-Sort