MergeSort

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: MergeSort

Beitrag von sab »

Hallo,

ich habe noch eine Frage zur Komplexität von MergeSort. Den Kritzeleien vom 26.04.2012 kann ich entnehmen, dass MergeSort in O(log n) liegt.
Allerdings wird mir die Folie 16, auf der \(2^i \le n \leftrightarrow i \ge log _2 \left(n \right)\) steht, nicht ganz klar. Wieso steht \(\ge\) für "log streng monoton steigend"?
Und in welchem Zusammenhang steht \(n * \frac{1}{2^i}\) mit \(log _2 \left(n \right)\)?

Ich stehte total auf dem Schlauch..
Danke schonmal!

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: MergeSort

Beitrag von Prof. Karsten Weihe »

sab hat geschrieben: ich habe noch eine Frage zur Komplexität von MergeSort. Den Kritzeleien vom 26.04.2012 kann ich entnehmen, dass MergeSort in O(log n) liegt.
In O(log n) liegt die Rekursionstiefe bei Mergesort :!:

sab hat geschrieben: Allerdings wird mir die Folie 16, auf der \(2^i \le n \leftrightarrow i \ge log _2 \left(n \right)\) steht, nicht ganz klar. Wieso steht \(\ge\) für "log streng monoton steigend"?
Die Monotonie des Logarithmus brauche ich als Argument, damit die Ungleichung nach der Logarithmisierung beider Seiten erhalten bleibt.

sab hat geschrieben: Und in welchem Zusammenhang steht \(n * \frac{1}{2^i}\) mit \(log _2 \left(n \right)\)?
Auf Folie 15 schreibe ich ja \(n\cdot\frac{1}{2^i}\leq 1\). Auf der linken Seite der Äquivalenz auf Folie 16 habe ich diese Ungleichung einfach umgestellt. Und die rechte Seite dieser Äquivalenz ergibt sich durch Logarithmisierung beider Seiten.

KW

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: MergeSort

Beitrag von sab »

Prof. Karsten Weihe hat geschrieben:In O(log n) liegt die Rekursionstiefe bei Mergesort :!:
sab hat geschrieben: Allerdings wird mir die Folie 16, auf der \(2^i \le n \leftrightarrow i \ge log _2 \left(n \right)\) steht, nicht ganz klar. Wieso steht \(\ge\) für "log streng monoton steigend"?
Die Monotonie des Logarithmus brauche ich als Argument, damit die Ungleichung nach der Logarithmisierung beider Seiten erhalten bleibt.
sab hat geschrieben: Und in welchem Zusammenhang steht \(n * \frac{1}{2^i}\) mit \(log _2 \left(n \right)\)?
Auf Folie 15 schreibe ich ja \(n\cdot\frac{1}{2^i}\leq 1\). Auf der linken Seite der Äquivalenz auf Folie 16 habe ich diese Ungleichung einfach umgestellt. Und die rechte Seite dieser Äquivalenz ergibt sich durch Logarithmisierung beider Seiten.
Alles klar, vielen Dank für die Erläuterungen!

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: MergeSort

Beitrag von sab »

Ich habe nochmal eine andere Frage:
Im Wiki (https://hermes.algo.informatik.tu-darms ... .php/Merge) heißt es bei Abstract View für Merge, dass die Abbruchbedingung \(i_1=|S_1|\) und \(i_2=|S_2|\) ist, das ist auch einleuchtend soweit.
Ich habe jetzt irgendeine Iteration in MergeSort, bei der ich jetzt zwei Singletons mergen möchte. Dann trifft ja sofort die Abbruchbedingung zu, also z.B. (5) und (4) sollen sortiert werden, da \(i_1=|S_1|\) gleich \(i_2=|S_2|\), nämlich jeweils i=1. Habe ich dann für einen kurzen Moment eine unsortierte Sequenz, nämlich (5,4), und diese wird dann im nächsten Schritt sortiert? Oder übersehe ich eine Bedingung, die so einen Fall ausschließt oder genauer beschreibt?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: MergeSort

Beitrag von JannikV »

i wird doch mit 0 initialisiert. Nimmt dann erst die 4 und das erste i ist gleich 1, nimmt dann die 5 und das zweite i ist gleich 1. Und dann gilt die Abbruchbedingung und die Liste ist grade {4, 5}

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: MergeSort

Beitrag von sab »

Danke, das stimmt natürlich - ich wusste, dass ich mich irgendwo vertue ;)

bagwell
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 109
Registriert: 15. Nov 2010 09:18

Re: MergeSort

Beitrag von bagwell »

Aus Abbruchbedingung und Variante folgt ja, dass der Algorithmus irgendwann terminiert. Dies trifft bei Mergesort in meinen Augen ohne weitere Erklärungen allerdings nicht zu, wenn ich das Wiki richtig verstehe.

Abbruchbedingung:

Code: Alles auswählen

i1=|S1| && i2 = |S2|
Variante:

Code: Alles auswählen

 i1+i2 += 1
Aus der Variante alleine wird nicht ersichtlich, dass spätestens nach |S1| Iterationen i2 erhöht wird, in dieser Form könnte die Variante doch auch bedeuten, dass i1 in jeder Iteration um 2 erhöht wird und i2 in jedem Schritt um 1 vermindert (bzw jedes andere Szenario, dass die Summe um 1 erhöht). i2=|S2| würde in diesem Szenario niemals erfüllt werden und die Abbruchbedingung wäre nie erfüllt.

Muss die Variante also nicht irgendwie erweitert werden?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: MergeSort

Beitrag von Prof. Karsten Weihe »

bagwell hat geschrieben:Aus Abbruchbedingung und Variante folgt ja, dass der Algorithmus irgendwann terminiert. Dies trifft bei Mergesort in meinen Augen ohne weitere Erklärungen allerdings nicht zu, wenn ich das Wiki richtig verstehe.
Ich habe die Variante jetzt entsprechend erweitert, danke :) und sorry :oops:

KW

thomasthomas
Neuling
Neuling
Beiträge: 9
Registriert: 19. Aug 2012 18:08

Re: MergeSort

Beitrag von thomasthomas »

Also bin nochmal das Beispiel vorgegangen:

543210
543 210 /Mergesort
5 43 2 10 /Mergesort
5 4 3 2 1 0 /Mergesort
45 3 12 0 / Merge
345 012 /Merge
012345 /Merge

Ist das richtig so? Wenn Merge-op spiegelsymmetrisch ist zu Mergesort, dann müsste doch beim 1. Merge Aufruf die 4 sich mit der verbinden oder?

Und wenn i = 2 wo stehe ich dann genau....beim 2. Mergeaufruf?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: MergeSort

Beitrag von JannikV »

Hi, die 5 Zeile, also dein erster Merge Aufruf ist nicht ganz korrekt. Da du vorher die Teilliste in 5 | 43 geteilt hast und 43 dann von einem nächsten Aufruf in 4 | 3 geteilt wird werden diese dann auch zuerst wieder zu 34 zusammengesetzt. Anschließend wird dann 5 | 34 zu 345 gemerged.

VG

thomasthomas
Neuling
Neuling
Beiträge: 9
Registriert: 19. Aug 2012 18:08

Re: MergeSort

Beitrag von thomasthomas »

Ah vielen Dank. Das macht Sinn. Und steh ich nach Iteration = 2 bei dem Ergebnis des 2. Mergeaufruf?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: MergeSort

Beitrag von JannikV »

Bei nem rekursiven Algorithmus von Iterationen zu sprechen ist nicht ganz leicht..

Aber nachdem die rekursiven Aufrufe vorbei sind, die hierarchisch auf Ebene 2 stattfinden hast du die beiden Listen 345 | 012

VG

Antworten

Zurück zu „Archiv“