Informatik Algorithmen – Mergesort und Divide-and-Conquer
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was ist das Prinzip von Divide-and-Conquer? · Welche drei Phasen durchläuft Divide-an…
Karten
14 KartenWas ist das Prinzip von Divide-and-Conquer?
Rückseite
Divide-and-Conquer teilt ein Problem in kleinere Teilprobleme, löst diese rekursiv und kombiniert die Teillösungen zur Gesamtlösung.
Welche drei Phasen durchläuft Divide-and-Conquer?
Rückseite
Die Phasen sind: Divide (Teilen), Conquer (Rekursiv lösen) und Combine (Zusammenfügen der Teillösungen).
Wie funktioniert Mergesort grob beschrieben?
Rückseite
Mergesort teilt das Array rekursiv in Hälften, sortiert diese und führt sie über das Merge-Verfahren sortiert zusammen.
Wie lautet die Laufzeitkomplexität von Mergesort?
Rückseite
Mergesort hat im Best-, Average- und Worst-Case eine Laufzeit von O(n log n).
Wie hoch ist der Speicherbedarf von Mergesort?
Rückseite
Mergesort benötigt zusätzlichen Speicherplatz von O(n) für das temporäre Array beim Zusammenführen.
Ist Mergesort ein stabiler Sortieralgorithmus?
Rückseite
Ja, Mergesort ist stabil, da beim Merge gleiche Elemente ihre relative Reihenfolge behalten.
Was passiert im Merge-Schritt von Mergesort?
Rückseite
Zwei bereits sortierte Teilarrays werden elementweise verglichen und in ein gemeinsames sortiertes Array kopiert.
Welche Rekursionsgleichung beschreibt Mergesort?
Rückseite
Die Rekursionsgleichung lautet T(n) = 2·T(n/2) + O(n) für das Zusammenführen.
Wann endet die Rekursion bei Mergesort?
Rückseite
Die Rekursion endet, wenn ein Teilarray der Länge 1 (oder 0) erreicht ist, da es dann bereits sortiert ist.
Wie unterscheidet sich Mergesort von Quicksort?
Rückseite
Mergesort garantiert O(n log n) im Worst-Case und ist stabil, Quicksort ist oft schneller, aber instabil und im Worst-Case O(n²).
Was ist der Unterschied zwischen top-down und bottom-up Mergesort?
Rückseite
Top-down nutzt Rekursion, bottom-up iteriert über steigende Teilarray-Größen und vermeidet Rekursionsoverhead.
Warum ist Mergesort meist nicht in-place?
Rückseite
Der Merge-Schritt benötigt ein temporäres Array, um Elemente ohne Überschreiben zusammenzuführen, was O(n) Extra-Speicher erfordert.
Für welche Datenstrukturen eignet sich Mergesort besonders?
Rückseite
Mergesort eignet sich gut für verkettete Listen, da kein zufälliger Zugriff nötig ist und der Merge pointerbasiert effizient funktioniert.
Wie kann man den Merge-Schritt effizient implementieren?
Rückseite
Man nutzt ein Hilfsarray, kopiert beide Hälften hinein und schreibt durch zwei Index-Variablen sortiert zurück ins Originalarray.