Merge-Sort Analyse

[Brombeere]

Hallo,

ich versuche gerade eine Vorlesung nachzuarbeiten und verstehe dabei folgendes Thema überhaupt nicht:

Gegeben ist ein Programmtext in Java:

static void merge(int[] a, int left, int middle, int right) {
 int[] b = new int[a.length];
 for (int k = left; k <= middle; ++k) { b[k] = a[k]; }
 for (int k = middle + 1; k <= right; ++k) {
  b[right + middle – k + 1] = a[k];
 }
 int i = left;
 int j = right;
 for (int k = left; k <= right; ++k) {
 if (b[i] < b[j]) { a[k] = b[i++]; }
 else { a[k] = b[j--]; }
 }
}

Hieraus soll nun eine Laufzeit bestimmt werden.

Als Herangehensweise wird gesagt, man solle die Rekursionsformel ablesen.

Diese lautet:
vereinfachende Annahme: n = 2k
T(n) = {O(1) für n=1
2 T(n/2) + O(n) für n > 1

Das erschließst sich mir leider überhaupt nicht. Wie kommt man darauf?

 

[SlaterB]

die gepostete merge()-Methode ist nur ein Teil von Mergesort, die Rekursion ist da gar nicht enthalten,

deine Frage ist wie man auf die Rekursionsformel kommt? denkbar einfach,
ob n oder k ist gar nicht so sehr wichtig, für kleines n/ k ist konstanter minimaler Aufwand klar,

bei dem Hauptfall, einer beliebig großen Liste, wird diese in zwei Teile getrennt,
also 2x der Aufwand für die Hälften noch nötig, sowie durch die aktuellen Arbeiten und auch später das merge()
noch linearer Aufwand, alle Elemente werden einmal oder auch gerne 2 oder 3x bearbeitet, konstanter Faktor ist egal

 

[Brombeere]

Also heißt das:
Was bedeutet dann konkret O(1), wenn n=1. Bedeutet dies, dass die Liste nicht geteilt wird und man daher nur linearen Aufwand hat?

Wenn n>1 ist, dann wird für T(n) einfach 2*T(n/2) + O(n) aufgerufen. n/2, weil die Liste halbiert wird und *2, weil man 2 Listen bearbeiten muss. Auch hier verstehe ich aber noch nciht genau, für was das O(n) steht. Ist das dann einfach für den Sortieraufwand (oder was meinst du mit "aktuelle arbeiten"?)

 

[Brombeere]

Konkret auf eine Aufgabe bezogen: Betrachtet wird ein Mergesort-Algorithmus mit leichter Veränderung. Das Array wird in drei Teile aufgeteilt und zum Mischen wird wiederholt das Minimum der drei vorderen Elemente bestimmt. Anzugeben ist eine Rekursionsformel und man soll die explizite Formel in O-Notation ableiten.

Also:
T(n)=3*T(n/3)+3n

Man teilt das Array also in drei gleich große teile: n/3. Mit 3 multipliziert muss es wegen der Teilung noch werden. Unsicher bin ich mir aber mit dem Sortieren. Um das Minimum eines der drei geteilten Arrays zu bestimmen, muss man ja die ganze Liste durchlaufen. Also wäre der Aufwand doch n, und das ganze drei mal.

 

[SlaterB]

> Bedeutet dies, dass die Liste nicht geteilt wird und man daher nur linearen Aufwand hat?
ja, wobei sogar nur konstanten Aufwand, O(1) statt O(n)

> Ist das dann einfach für den Sortieraufwand (oder was meinst du mit "aktuelle arbeiten"?)
das ist alles was nicht durch die Rekursion einem anderen Schritt zugeordnet wird,
die Listen aufsplitten, was immer dabei zu tun ist, und sei es nur einen Mittel-Index berechnen, und später wieder mergen,

dafür kann die Liste wie gesagt auch 3x oder 5x durchlaufen werden, 5n ist auch wieder n,
ein konstanter Faktor spielt keine Rolle wenn n in die Millionen geht und n^2 entsprechend schlimm wäre,
dagegen ist 5n praktisch n

wie hoch n bei der neuen Formel ist egal, schreibe O(n) wie zuvor

 

[Brombeere]

Und meine aufgestellte Rekursionsformel, ist die korrekt?

 

[Fant]

Ohne die Implementierung zu kennen ist das nicht sicher zu beantworten, doch es sieht ganz vernünftig aus. Um nun die Laufzeit des gesamten Algo. zu bestimmen lautet das Stichwort: Master-Theorem.

Gruß Fant

 

[Brombeere]

Master Theorem hatten wir in der Vorlesung nicht.

Ich hätte jetzt einfach geschlussfolgert:
3*T(n/3)+3n
<=9*T(n/9)+12n
...
<=3^iT(n/3^i)+(3^i+3)n

<=n T(1) + log2(n) //vermutlich falsch

Nach der vorletzten Zeile komm ich nicht weiter.

 

[Fant]

Mach deine Überlegungen zunächst mal für 3-er Potenzen, also für solche Zahlen n für die es ein k gibt mit n=3^k.

Gruß Fant

 

[Brombeere]

Also ich habe jetzt meine Rekursionsformel zur Bestimmung der Laufzeit. Abschätzen möchte ich dies nun in O-Notation (für n=1 lautet meine Rekursionsformel übrigens O(1)).

Verstehe jetzt leider nicht, warum ich das ganze für 3^i betrachten soll.

Das wäre doch die Menge {3,9,27...}.
Also T(3)=2T(3/3)+3*3=2T(1)+9
T(9)=2T(9/3)+9*3=2T(3)+27
...


In unserer Vorlesung haben wir das so weitergeleitet bez. des Beispiels von oben:
T(n) ≤ 2 T(n/2) +cn
≤ 2 [2T(n/4) + c(n/2)] + cn
≤ 4 T(n/4) + 2cn
≤ 8 T(n/8) + 3cn
...
≤ 2i T(n/2i) + icn
...
≤ n T(1) + c n log 2n
≤ c n + c n log n
= O(n log n)

Ähnliches ergibt sich ja auch bei der nun vorliegenden Aufgabe. Nur verstehe ich den Schritt nach den zweiten ... in der Vorlesung schon nicht.

 

[Fant]

Heb mal hervor, welchen Schritt du nicht verstehst. Mir jedenfalls ist das gerade nicht klar...


Mein Tipp war so gemeint:

Untersuche die Laufzeit von T[n], indem du annimmst n sei eine 3er Potenz mit n=3^k. Dann kannst du auf den Ausdruck T[n] genau k-mal die Rekursionsformel anwenden und "es kommt am Ende was schönes raus".

 

[Brombeere]

≤ 2i T(n/2i) + icn
...
≤ n T(1) + c n log 2n

Die Bildung der ersten Zeile ist mir klar. Aber wie kommt man nun auf "n T(1) + c n log 2n" und weiter dann auf
"≤ c n + c n log n
= O(n log n)"

 

[Fant]

Da wurde das gleich gemacht, was ich dir vorgeschlagen habe. Man nimmt an n sei (diesmal) eine 2er-Potenz, dann kannst du n schreiben als 2^i (Da ist ein Tippfehler(?) bei dir).

Beim letzten Schritt lässt man das n einfach unter den Tisch fallen, da es im Vergleich zu n*log(n) für große n nicht mehr ins Gewicht fällt.

 

[Brombeere]

Ja, das ist ein Schreibfehler.
Also setzt man n=2^i und es kürzt sich viel heraus. Wie ist es eigentlich mit den Indizes. In der Vorlesung wurde n=2^k gesetzt. Streng genommen steht also da:
T(2^k/2^i). Das kürzt sich aber nicht zu 1.

T(1) ist ja O(1). Warum wird das nun zu c. Also konkret die letzten drei Zeilen:
≤ n T(1) + c n log 2n
≤ c n + c n log n//der 2 logarithmus zur basis n wird vermutlich einfach vereinfach zu log n, weil der rest nicht ineressiert
= O(n log n)//Wie ergibt sich das?

 

[Paddelpirat]

T(1) ist ja O(1). Warum wird das nun zu c.

Kennst du überhaupt die Definition der O-Notation? Stichwort: Landau-Symbole.

Landau-Symbole ? Wikipedia

 

[Fant]

Hast du schon wieder alles vergessen, was in den vorherigen Postings stand? ^.^

Setzt man n = 2^k, und wendet die Rekursionsformel i-mal an, dann steht da tatsächlich T[2^k/2^i]. Wenn du die Rek.-Formel aber genau k-mal anwedest, dann steht da T[2^k/2^k].

T[1] liegt hier in O(1), genau. Das heißt aber doch nur, dass die Auswertung von T[1] in konstanter Zeit erfolgt. Das heißt egal wie groß n zuvor gewählt war brauchst du für die Auswertung von T[1] meinetwegen 3 oder 10 oder 20 Rechenoperationen o.Ä. Wie groß diese Zahl genau ist, interessiert aber nicht, sondern nur, dass sie nicht mehr von n abhängt. Man nennt sie einfach c. Und um da weiterer Verwirrung vorzubeugen: Das ist in der Regel auch nicht das gleiche c, wie es im zweiten Summanden vorkommt. Wichtig ist in beiden Fällen nur, dass es irgendeine Konstante Zahl ist.

Welcher Logarithmus da steht ist vollkommen egal. Du kannst eine beliebige Basis wählen. Logarithmen einer Zahl zu unterschiedlichen Basen unterscheiden sich nur um einen konstanten Faktoren, der von den beiden Basen abhängt. Den Faktor kannst du dann auch einfach in deiner Konstanten Zahl c verpacken. Bei der Laufzeitanalyse spielt das keine Rolle

 

[Brombeere]

Dann versuche ich nun einmal die Aufgabe zu beenden:

Ich hatte:

T(n)=T(n/3)+3n
<=9T(n/9)+12n
<=27T(n/27)+30n
...
Hieraus ergibt sich
3^iT(n/3^i)+3^i+3
Setzt man n=3^k, wie in der Aufgabenstellung folgt mit k-maliger Anwendung der REkursionsformel:
n * T(1)+n+3
T(1) ist in O(1). Also c:
cn+n+3.

 

[Fant]

T(n)=T(n/3)+3n

Das hier passt noch...

<=9T(n/9)+12n

...aber hier wird es schon falsch. Was rechnest du denn da?

 

[Brombeere]

Na ja:

Wenn T(n)=T(n/3)+3n gilt, dann muss ich doch T(n/3) aufrufen:
T(n/3)=T((n/3)/3)+3*n/3=T(n/9)+n
Dann T(n/9) aufrufen...
...
T(n/3^i)+n
Dann n=3^k setzen und mit k-maliger ausführung folgt:
T(3^k/3^k)+3^k
=T(1)+3^k
=c
Ich bin aber eigentlich davon ausgegangen, dass gilt:
T(n)=3*T(n/3)+3n
So kommen dann auch meine Zahlen zustande. n/3, weil ich die Liste drittele. Und drei mal, weil ich alles dreimal machen muss. +3n dann noch, weil man einmal jede Liste durchlaufen muss.

 

[Fant]

Ich bin aber eigentlich davon ausgegangen, dass gilt:
T(n)=3*T(n/3)+3n

Ja, DAS gilt. Da hab ich mich oben verguckt ... das passt aber nicht zu deinen Zahlen, die du da ausrechnest ???:L

 

[Brombeere]

Also noch mal:

T(n)=3*T(n/3)+3n

Nun muss ich doch T(n/3) aufrufen. Ich setze also in obige Funktion n/3 ein.
Also:
T(n/3)=3*T((n/3)/3)+3*n/3=3*T(n/9)+n
Jetzt dann in die erste Funktion n/9 einsetzen, aber hier sehe ich glaube ich gerade den fehler. Wo muss ich jetzt die n/9 einsetzen?

 

[Fant]

Wenn T[n]=3*T[n/3]+3n und T[n/3] = 3*T[n/9]+n, dann ist T[n] = ... ? Macht es immer noch nicht "klick"? ^_^

 

[Ein Kasseler]

Hallo Brombeere,

schau dir mal Folie 58 an und versuche die Zeile, die zwischen den Punkten steht nachzuvollziehen.

Viele Grüße!
Ein Kasseler

 

[Brombeere]

Dann müsste (wenn ich mich nicht verrechnet habe) (*)T(n)=9*T(n/9)+12n sein.
Jetzt kann man dann wieder T(n/9) berechnen:
T(n/9)=3*T(n/27)+3*(n/9)=3*T(n/27)+1/3*n.
Das kann man nun wieder in die Gleichung (*) einsetzen:
T(n)=9*(3*T(n/27)+1/3*n)+6n=27T(n/27)+9n.

Also insgesamt:
T(n)=3*T(n/3)+3n
<=9*T(n/9)+6n
<=27*T(n/27)+9n
<=81*T(n/81)+12n
...
<=3^iT(n/3^i)+3i

<=n T(1)+3 log3(n)
<=c n + log (n)

=O(n log(n))

Jetzt sollte es aber stimmen?

 

[Fant]

Hier:

<=81*T(n/81)+12n
...
<=3^iT(n/3^i)+3i

und hier:

<=c n + log (n)
=O(n log(n))

haben sich noch zwei Fehler eingeschlichen.

 

[Brombeere]

Zu 1:
<=81*T(n/81)+12n
...
<=3^iT(n/3^i)+3in

Da hat das n hinten gefehlt.

Zu 2:
c n + log(n) stimmt meiner Meinung. Summanden niedriger Ordnung fallen weg: log n wächst langsamer als n, also:
O(n)

 

[Brombeere]

In O-Notation:

O(log(n)*n), fällt mir gerade noch auf. Weil es gilt ja: T(n)<=3^iT(n/3^i)+3in<=n + log3(n)*n.

 

[Fant]

Jetzt passt alles. (abgesehen von eventuellen Konstanten Faktoren, die für deine Laufzeitanalyse keine Rolle spielen)

Nun solltest du dir aber vielleicht noch klar machen, wieso es ausreichend ist den allgemeinen Fall, dass n wirklich eine 3er-Potenz ist, zu betrachten.