Willkommen zurück zur Vorlesung Effiziente Algorithmen.
Wir sind heute ein bisschen ausgedünnt, nur drei Studenten anwesend.
Ich schiebe das einfach mal auf das schlechte Wetter.
Herr Schmeck ist heute leider verhindert, deshalb werde ich ihn in der
Vorlesung vertreten.
Und dann fangen wir gleich an.
Wir haben letztes Mal das Kapitel 3 abgeschlossen, Algebraische
Probleme.
Und in diesem Kapitel haben wir auch schon ein paar Aspekte des Themas
behandelt, das wir uns heute anschauen, und zwar Rekurrenzgleichungen.
Wenn Sie sich erinnern, Straßen beispielsweise, da haben wir auch eine
Rekurrenzgleichung aufgestellt, weil das ein gewaltiger Konker
-Algorithmus ist.
Und wir werden uns heute anschauen, wie man allgemein, also wie man
Rekurrenzgleichungen aufstellt, wie man mit denen umgeht, wie man aus
einer Rekurrenzgleichung eine Laufzeit bestimmen kann.
Lösung von Rekurrenzgleichungen, das wurde auch schon mal in Info 2
kurz angesprochen.
Wir werden hier an der Stelle noch ein paar andere Aspekte beleuchten.
Und zwar, Ausgangssituation ist, wir haben ein Divide-and-Conquer
-Algorithmus und wir möchten den Berechnungsaufwand dafür bestimmen.
Also wie aufwendig ist es, ein gegebenes Problem mit diesem Divide-and
-Conquer -Algorithmus zu lösen.
Und hierfür geben wir von vornherein Voraussetzungen aus.
Also wir haben hier ein Problem P, das besitzt die Größe N, wie immer
unsere Eingabegröße N.
Und dieses Problem, das teilen wir auf jeder Rekursionsebene in K
-Teilprobleme.
Das heißt, diese K-Teilprobleme hier, P1 bis PK durchindiziert und
jedes dieser Teilprobleme hat die Größe N durch C.
Okay.
Das heißt, wir teilen auf.
Als nächstes lösen wir diese Teilprobleme rekursiv, indem wir für
jedes einzelne Teilproblem dieses Divide-and-Conquer-Verfahren nochmal
aufrufen.
Das heißt, wir lösen diese einzelnen Probleme, P1 bis PK, rekursiv
nach dem Verfahren, solange diese Problemgröße, die wir da lösen, noch
größer ist als 1.
Das heißt, man könnte auch schon früher abbrechen, wenn man effizient
das Verfahren kennt, das ab einer bestimmten Größe anwendbar ist.
Aber grundsätzlich nur, wenn wir eine bestimmte Rekursionstiefe
erreicht haben, dann lösen wir das Problem direkt.
Das heißt, wenn dieses Problem so weit runtergebrochen wurde, dass es
einfach genug ist, direkt zu lösen, dann lösen wir es direkt.
Nachdem wir jetzt diese Teilprobleme gelöst haben, müssen wir die
wieder zusammenfügen.
Indem wir diese Lösung wieder zusammenfügen, kombinieren wir diese
Teillösung in die gesamte große Lösung unseres ursprünglichen Problems
L von P. Das heißt, das Ganze hier auf der rechten Seite nochmal
schematisch aufgezeichnet.
Wir haben hier unser Ursprungsproblem P, das wird zerteilt in einzelne
Teilprobleme, P1 bis PK.
Diese einzelnen Probleme werden gelöst, rekursiv.
Dadurch erzeugen wir diese Teillösung L1, L2, LK und die fügen wir
wieder zusammen und bekommen dadurch die Gesamtlösung des Problems.
Bei Straßen war das beispielsweise, wir haben diese Matrix, diese
Ursprungsmatrix, die wir hatten, A und B.
Die haben wir jeweils zerteilt in Teilmatrizen, in 2x2-Matrizen.
Also das Feld entsprechend, die große Matrix, partitioniert in vier
Teilfelder.
Die haben wir dann rekursiv miteinander multipliziert und dann später
durch Addition und Subtraktion wieder zusammengefügt.
Okay, wenn wir uns jetzt anschauen, wie ist denn jetzt der
Zeitaufwand, wenn wir dieses Verfahren rekursiv anwenden?
Okay, wir haben zunächst mal natürlich den Aufwand dafür, wenn wir das
Problem direkt lösen, auf der untersten Ebene.
Das ist hier dieses A.
Das ist entweder, wenn das Problem die Größe 1 erreicht hat oder
entsprechend wir tief genug auf dem Rekursionsraum angekommen sind,
sodass wir das Problem direkt lösen können.
Und dann haben wir ja noch den Aufwand auf jeder Rekursionsebene für
diese Schritte A und C.
Also einmal für das Aufteilen und dann wieder für das Zusammensetzen.
Und das wird hier mit diesem G von N bezeichnet.
Das ist der Aufwand, der zum Zerteilen und Zusammenfügen der
Teillösung, der auf jeder Rekursionsebene entsteht.
Das heißt, wenn wir das zusammenfassen, wenn wir auf der untersten
Ebene angekommen sind, dann lösen wir das Problem direkt.
Wir haben einen Aufwand von A auf einer beliebigen Rekursionsebene T
von N.
Wir erzeugen k Teilprobleme und jedes dieser Teilprobleme hat die
Größe N durch C.
Der Aufwand entsteht und zusätzlich noch dieser Aufwand D von N, der
durch das Zusammenfügen und Zerteilen der einzelnen Probleme besteht.
Wir gehen im Folgenden davon aus, dass die Dividend-Conquer
-Algorithmen, die wir betrachten, nach folgendem Schema arbeiten.
Es gibt auch andere Dividend-Conquer-Algorithmen, beispielsweise wo
ich keine fixe Zerteilung habe, also wo die Anzahl der Teilprobleme
nicht vorgegeben ist, sondern dass sie beispielsweise auch von N
abhängt.
Es könnte natürlich auch sein, dass mein Problem sich nicht um einen
fixen Bruch verkleinert pro Rekursionsebene, sondern immer nur zum
Beispiel um 1.
Das ist auch möglich.
Wie löst man jetzt so eine Rekursionsgleichung auf, die in folgender
Gestalt gegeben ist?
Okay, da gibt es ein sehr schönes Lemma.
Das heißt, wenn wir N so darstellen können, als ein Vielfaches von C,
also N gleich C hoch M, dann können wir den Aufwand, der durch Lösen
dieser Rekursionsgleichung entsteht, durch folgende Gleichung
darstellen.
Das ist ein einfacher Induktionsbeweis, den kann man zeigen, den
betrachten wir an der Stelle nicht.
Aber diese Gleichung an sich ist ja noch immer relativ unhandlich, um
damit schnell eine Analyse zu machen, weil hier muss man erst die
einzelnen Bestandteile in diese Formel einsetzen und das dann Schritt
für Schritt auflösen.
Das heißt, schauen wir uns doch erstmal Spezialfälle an, bevor wir
irgendwie zu einer allgemeinen Herangehensweise kommen, um solche
Gleichungen aufzulösen.
Okay, gehen wir mal davon aus, dass wir einen konstanten Aufwand haben
auf jeder Rekursionsebene.
Das heißt, der Aufwand, der entsteht für das Zerlegen und
Zusammensetzen der Teilprobleme, ist konstant und hängt nicht von der
aktuellen Problemgröße ab.
Okay, schauen wir uns mal den Fall an, wenn K gleich 1 ist.
Das heißt, ich erzeuge pro Rekursionsebene immer nur ein neues
Teilproblem.
Das heißt, ich verkleinere mein Problem eigentlich immer nur und
erzeuge keine neuen Probleme.
Dann bekomme ich folgenden Aufwand.
Logarithmus zur Basis c von n.
Wir haben ja in der Übung gelernt, die Basis ist egal, die können wir
rausziehen.
Das heißt, wir haben hier eigentlich logarithmischen Aufwand.
Warum ist das so?
Man kann sich das überlegen.
Logarithmus zur Basis c von n gibt ja die Anzahl der Rekursionen an.
Wenn ich konstanten Aufwand habe und immer nur ein Problem erzeuge,
ist Logarithmus zur Basis c von n die Anzahl der Rekursionen, die ich
zurücklege.
Das heißt, dadurch, dass mein Aufwand konstant ist, ich habe immer
einen Aufwand von d auf jeder Ebene, habe ich d mal Logarithmus von n,
das ist mein Aufwand, d ist meine konstante Feldwelle.
Was passiert, wenn ich mehr als ein Problem erzeuge?
Pro Rekursionsebene, dann komme ich hier auf so einen Ausdruck.
n hoch Logarithmus zur Basis c von k.
Ohne jetzt zu sehr in die Mathematik einzusteigen, wie da der genaue
Beweis dahinter ist, man kann sich ungefähr überlegen, dass dieser
Term hier, n hoch Logarithmus zur Basis c von k, dass es der Anzahl
der Teilproblemen entspricht, die während der gesamten Rekursion
erzeugt werden.
Okay, wir können uns auch noch den Spezialfall anschauen, wenn d von n
linear ist, das heißt exakt linear.
Der Aufwand, den ich auf jeder Ebene zusätzlich habe, ist immer linear
in der aktuellen Problemgröße.
Okay, wenn ich jetzt hier den Fall habe, dass die Anzahl der
Teilprobleme, die ich erzeuge, ist nochmal geringer als der Bruch, den
ich erzeuge, also diese Rate, mit der sich die Probleme verkleinern,
dann ja, das ist ein Fall, in dem dieses Problem, das ich per
Rekursion löse, sehr schnell klein wird, der Aufwand.
Das heißt, der Aufwand, der durch die Rekursion entsteht, der ist
wesentlich geringer im Vergleich zu dem Aufwand, der auf jeder Ebene
entsteht und dann komme ich auch hier bei linearer Laufzeit raus.
Wenn k gleich c ist, das heißt Verkleinerung und Anzahl der
Teilprobleme, die halten sich so die Waage, kann man sagen, dann komme
ich hier auf die Laufzeit n log n.
Hier kann man sich auch wieder überlegen, ich habe hier wieder eine
Rekursionstiefe von Logarithmus von n und auf jeder Ebene, also wenn
ich alle Teilprobleme einer Ebene betrachte, also über alle
Teilprobleme hinweg, dann habe ich linearen Aufwand, dadurch n mal log
n.
Und der zweite Fall, wenn die Teilprobleme viel mehr sind wie die
Reduktion in der Größe, dann komme ich entsprechend auf diesen
Ausdruck, o von n hoch Logarithmus zur Basis c von k.
Und das ist doch relativ erstaunlich, weil das genau der gleiche Fall
ist, wie wenn ich hier oben nur konstanten Aufwand habe.
Das heißt, speziell diese beiden Fälle hier, wie man denn da drauf
kommt, das schauen wir uns gleich an.
Das war mit dem sogenannten Mastertheorie.
Das heißt, wer sich das nochmal genauer anschauen möchte, wie man auf
diese einzelnen Ergebnisse kommt, wie man das formal herleitet, der
sei an das Buch von Korman verwiesen.
Sehr gutes Buch, da wird das nochmal ausführlich dargestellt, wie man
auf diese Erkenntnisse kommt.
Okay, was können wir aber daraus schon mal als Folgerung festhalten
für die Zeitkomplexität von einem Divide-and-Conquer-Verfahren?
Das heißt, wir haben einmal, also der Aufwand, den wir benötigen für
die Lösung, der hängt einmal ab für die direkte Lösung bei dem Abbruch
des Verfahrens.
Das heißt, auf der untersten Ebene, wenn ich keine Rekursionen mehr
durchführe.
Dann hängt es vor allem ab für den Aufwand B von N, der für jedes
einzelne Teilproblem entsteht.
Das heißt, einmal für das Aufteilen der Teilprobleme und dann wieder
für das Zusammensetzen der Teillösungen.
Und außerdem, was hängt es noch ab?
Natürlich von der Anzahl der Teilprobleme K, die ich überhaupt erzeuge
in jedem einzelnen Rekursionsschritt, für jedes einzelne
Rekursionsproblem und auch für die Größe der Teilprobleme.
Das heißt, wenn diese Probleme sehr schnell sehr klein werden, ist der
Aufwand natürlich geringer, wie wenn sie sich nur relativ langsam
verkleinern.
Wie man jetzt allgemein solche Rekurrenzgleichungen löst, die nach
diesem Schema gegeben sind, kann man durch das Mastertheorem auflösen.
Das Mastertheorem ist gewissermaßen ein Rezept für die Lösung für
Rekurrenzgleichungen.
Der Beweis, also die theoretischen Hintergründe, die betrachten wir
jetzt hier auch nicht.
Das kann man auch im Kormor nachlesen, sondern wir geben direkt zu den
Ergebnissen über.
Das heißt, wir haben als Voraussetzung, also wir betrachten hier
wieder Rekursionsgleichungen nach folgendem Schema.
T von N gleich K mal T von N geteilt durch C plus D von N.
Das heißt, wir setzen voraus, dass mindestens ein neues Teilproblem
erzeugt wird.
Das muss sein.
C ist der Aufwand, der entsteht für das Zerteilen der Teilprobleme und
das Zusammensetzen der Teillösungen.
Also K gibt die Anzahl der Teilprobleme an und C, also der Grad, um
wie viel sich das Problem pro Rekursionsebene verringert, der Anbruch.
Und genau deshalb muss C natürlich auch größer 1 sein, weil wenn C
gleich 1 wäre, würde sich das Problem durch die Rekursion nicht
verringern.
Wenn C sogar kleiner als 1 wäre, würde unser Problem größer werden
durch die Rekursion.
Also diese Bedingungen müssen immer erfüllt sein, bevor man das
Mastertheorem anwenden kann.
Auch ganz wichtig, K und C dürfen nicht von N abhängen.
Das müssen Konstanten sein.
D entsprechend muss eine Funktion sein, die von den ganzen Zahlen auf
die reellen Zahlen abbildet.
Hier steht zusätzlich noch diese Bedingung positiv.
Das muss nur für hinreichend große N geprüft werden.
Also man muss nur sicherstellen, dass diese Funktion für hinreichend
große N positive Werte liefert.
Das kann ja zum Beispiel sein, wenn man eine Rekursionsformel hat,
dass die für sehr kleine N negative Werte erzeugt.
Wenn das Rekursionsverfahren schon vorher abbricht, weil es eine
direkte Lösung findet für die entsprechende Problemgröße, dann wäre es
ja unsinnig weiter vorauszusetzen, dass diese Funktion positive Werte
liefern muss, wenn die für solche kleinen Werte gar nicht mehr
verwendet wird.
Natürlich kann man hier noch anmerken, häufig ist es natürlich so,
dass dieses N durch C in der Praxis kein exakter Wert ist, sondern
dass da irgendein Bruch rauskommt, eine Kommazahl.
Das heißt, wir gehen immer davon aus hier in dieser Analyse, dass wir
entweder aufrunden oder abrunden.
Das heißt, für das Mastertheorem gibt es drei Fälle, die wir
betrachten.
Diese Betrachtung richtet sich immer, wir vergleichen den Aufwand für
das Zusammensetzen und Zerteilen der Probleme mit dem Aufwand, der
durch die Rekursion entsteht.
Das heißt, wir prüfen hier immer, ob diese Funktion D von N, ob die in
einer bestimmten Komplexitätsklasse liegt.
Für den ersten Fall prüfen wir, ob D von N nach oben beschränkt ist
durch N-Hochligarithmus zur Basis C von K minus irgendeinem Epsilon.
Das heißt, dieses Epsilon, es muss eine echte reale Zahl geben, größer
gleich Null, die wir hier noch einfügen können, sodass D von N in
dieser Komplexitätsklasse liegt.
Wenn das der Fall ist, dann bekommen wir als Ergebnis, dass T von N,
also exakt in der Komplexitätsklasse, durch Theta hier, N
-Hochligarithmus zur Basis C von K liegt.
Als nächstes haben wir den Fall, wenn D von N exakt in dieser Klasse
liegt, also N-Hochligarithmus zur Basis C von K.
Das heißt, hier gibt es kein Epsilon, muss exakt in der Klasse liegen.
Dann ist T von N liegt dann in der Klasse Theta von N-Hochligarithmus
zur Basis C von K mal Logarithmus von N.
Man kann das ja so interpretieren, dass hier als Aufwand er eben noch
durch die Rekursion zusätzlich dazukommt.
Und der letzte Fall, da wird dann D von N nach unten beschränkt durch
N -Hochligarithmus zur Basis C von K.
Auch hier, es muss ein Epsilon existieren, ein echtes Epsilon, damit
es in der Klasse liegt.
Ansonsten würden wir ja in den Fall B zurückfallen.
Und damit ist es allerdings noch nicht getan bei dem dritten Fall und
da ist noch eine weitere Bedingung, die wir sicherstellen müssen, und
zwar folgende.
Das heißt, K mal D von N geteilt durch C muss kleiner gleich sein als
Alpha mal D von N.
Auch hier für irgendein Alpha kleiner gleich echt kleiner 1 und für
alle genügend großen N.
Das heißt, es ist nicht wichtig, dass das für alle N erfüllt ist,
sondern, wie in der asymptotischen Betrachtung, wir müssen irgendein N
mal festlegen.
Und wir können dann ab diesem N sagen, wir können dafür ein Alpha
bestimmen, zeigen, dass die Gleichung erfüllt ist und dann liegt T von
N in der Komplexitätsklasse, die durch D von N vorgegeben wird.
Okay, das heißt, um es nochmal zusammenzufassen, wenn man sich das
hier alles anschaut, die Lösung der Rekurrenzgleichung, die hängt
davon ab, welche der Funktionen D von N und N hoch Logarithmus zur
Basis C von K stärker wächst.
Das heißt, ob der Aufwand auf jeder einzelnen Ebene für jedes
Teilproblem größer ist oder ob der Aufwand, der durch die Rekursion
entsteht, größer ist.
Das heißt dadurch, ob ich mehr Probleme lösen muss oder mehr Aufwand
dadurch habe, dass ich einzelne Probleme löse.
Und an der Stelle auch ein paar kleine Beispiele.
Wir haben hier zum Beispiel 9 mal T von N Drittel plus N, T von 2
Drittel N plus 1 oder auch T von N von 2 mal T von N Halbe plus N Log
N.
All diese Beispiele hier kann man mit dem Mastertheorium lösen und ja,
dazu wird es auf jeden Fall auch Übungsaufgaben geben auf dem nächsten
Übungsblatt.
Um das mal beispielhaft durchzuexerzieren für das erste Beispiel, das
da angegeben war.
Das war T von N ist gleich 9 mal T von Drittel plus 1.
Was wir als erstes machen, wir bestimmen die Konstanten.
Wie viele Teilprobleme werden erzeugt?
9 Stück.
Was heißt K?
Wie ist das Verhältnis zwischen Ursprungsproblem und nächstkleinerem
Problem, also auf der nächsten Rekursionsebene?
Hier steht eine 3, das heißt das Problem verringert sich um den Faktor
3.
Das heißt, C ist gleich 3.
Und schließlich der Aufwand, der auf jeder Ebene entsteht, ist linear.
K ist N, steht hier, das heißt, D von N ist gleich N.
Was wir als nächstes noch berechnen müssen, ist diese Ausdruck hier,
Logarithmus zur Basis C von K.
Das steht hier, Logarithmus zur Basis 3 von 9, das ist 2, weil 3 hoch
2 ist gleich 9.
Das heißt, das ist auch schnell abgehandelt.
Okay, wie gehen wir dann vor?
Dann prüfen wir eigentlich die einzelnen Fälle durch.
Hier ist es relativ offensichtlich, das sieht man direkt.
Wir haben D von N ist gleich N.
Und das wird nach oben beschränkt durch O von N hoch Logarithmus zur
Basis C von K minus Epsilon.
Und das ist nichts anderes als O von N hoch 2 minus Epsilon.
Okay, das heißt, wir sehen, hier haben wir N, das ist N hoch 1, auf
der anderen Seite N hoch 2 minus Epsilon.
Was folgen wir daraus?
Also es gibt auf jeden Fall dieses Epsilon.
Und dieses Epsilon kommt im Intervall 0,1, im offenen Intervall 0,1.
Das heißt, für alle Epsilon, die sich in diesem Intervall befinden,
für die ist diese Gleichung erfüllt.
Das heißt, Fall A des Mastertheorems trifft zu.
Und das bedeutet, T von N liegt in der Komplexitätsklasse Theta von
N².
Man sieht, der Bildschirm hat leider einen kleinen Blaustich, aber man
sieht das Ergebnis eindeutig.
Also das ist ein relativ einfaches Konzept, das sich direkt anwenden
lässt und eben sehr nützlich ist, gerade in der Praxis für
Rekursionsverfahren, um deren Aufwand zu bestimmen.
Gut, und das war ein relativ kurzes Kapitel.
Das heißt im Endeffekt nur so ein kleiner Einschub, wie man eigentlich
mit Rekursionsgleichungen umgeht.
Und das ist also ein wichtiges Thema, das für die ganze Vorlesung
relevant ist, das uns immer wieder begegnen wird.
Und als nächstes, Frage dazu, ja?
Warum ist es genau Theta?
Warum es genau Theta ist, das ergibt sich natürlich aus dem Beweis,
der im Common-Buch ist.
Aber das Schöne daran ist natürlich auch, dass man wirklich eine
exakte Klasse festlegen kann.
Weil wenn ich nur O habe, dann weiß ich ja nicht, wie klein die
Funktion ist.
Zum Beispiel N wird ja auch durch N hoch N.
Also N liegt auch in O von N hoch N.
Das heißt, die Aussage, die der Wanderer durchgeneriert ist, ist nicht
sehr aussagekräftig.
Eben dadurch, dass man dieses Theta hat.
Also wenn man diese Rekursionsbäume im Endeffekt erzeugt und sich
anschaut, wie viel Aufwand da ersteht auf jeder Ebene, dann kann man
diese Ergebnisse herleiten und kommt dann auf diesen Theta-Ausdruck.
Okay, damit sind wir auch schon beim nächsten Thema und zwar Suchen
und Sortieren.
Okay, was versteht man denn unter Suchen und Sortieren?
Das heißt, die Objekte, mit denen wir uns hier beschäftigen, das sind
erstmal Listen.
Moment.
Das sind erstmal Listen.
Und in diesen Listen sind Elemente einer geordneten Menge gespeichert.
Okay, was genau bedeutet das denn eigentlich?
Also wir haben hier ein Universum U, aus dem unsere Elemente kommen.
Das können natürliche Zahlen sein, Buchstaben, aber auch Instanzen von
Klassen oder ganz abstrakte Gebilde.
Wichtig ist nur, dass diese Elemente irgendwie vergleichbar sind durch
eine Ordnungsrelation.
Also je zwei Elemente aus diesem Universum müssen miteinander
vergleichbar sein.
Das heißt, wie die vergleichbar sind, das ist erstmal egal.
Wir müssen nur sicherstellen, dass sie entsprechend vergleichbar sind.
Das heißt, diese Elemente, die wir vergleichen, das sind Such- und
Sortierschlüssel.
Das ist eigentlich das Entscheidende.
Und wie schon gesagt, es können Namen, Zahlen etc.
alles mögliche sein, aber eben auch komplexe Konstrukte, Records, also
Instanzen von Klassen beispielsweise.
Wenn ich eine Person in Java abbilde beispielsweise, dann hätte ich ja
Name, Vorname, Nachname, Geburtsdatum etc.
Und ich muss nur irgendeine Basis dieser Daten, nur irgendeine
Vergleichsoperation definieren.
Und diese Vergleichsoperation, die muss natürlich eindeutig sein.
Das heißt, ich muss jedes einzelne Element miteinander vergleichen
können.
Und diese Ordnung muss auch transitiv sein.
Ansonsten keine eindeutigen Wertfragen.
Die Listen erstmal nicht, das wird erst interessant, wenn man
bestimmte Operationen darauf ausführt.
Weil dann kann ja sein, wenn ich genau eine doppeltverkettete Liste
habe, kann ich ja auch rückwärts traversieren.
Für manche Operationen ist es wichtig, dass man das machen kann.
Aber dazu kommen wir gleich noch.
Wenn wir uns dann ja über Zugriffszeiten für bestimmte Operationen
unterhalten.
Das heißt, die Problemgröße, die wir hier betrachten, ist immer die
Länge der Liste.
Entscheidend ist nur, wie viele Elemente in der Liste gespeichert
sind.
Das heißt, die Größe der Listen-Elemente selbst ist egal.
Die ist nicht relevant für das Problem.
Aber die Anzahl der Elemente, die gespeichert werden.
Was für Datenstrukturen können wir da verwenden?
Wir können entweder ein Array oder ein Vektor verwenden.
Das heißt, jedem Element ist ein eindeutiger Index zugewiesen.
Und dadurch haben wir auch wahlfreien Zugriff.
Das bedeutet, ich kann jedes Element, das in diesem Array oder Vektor
gespeichert ist, direkt adressieren.
Wenn ich den Index scanne.
Man kann hier natürlich auch andere Datenstrukturen verwenden, die
sequentiellen Zugriff haben.
Das ist einmal die linearverkettete Liste, die einmal den Kopf hat.
Das heißt, wenn ich auf das ente Folgeglied zugreifen möchte, muss ich
vom Kopf bis zum enten Folgeglied durchiterieren.
Über die einzelnen Elemente in der Liste.
Also die linearverkettete Liste.
Dann gibt es auch noch die doppeltverkettete Liste.
Da kann ich einmal das... also vorwärts und rückwärts iterieren.
Ich habe den Kopf und das Ende der Liste.
Je nachdem, auf welches Element ich zugreifen möchte, kann es mehr
Sinn machen.
Ich fange eben an, von vorne zu iterieren oder von hinten.
Eine andere Möglichkeit wäre auch, die Elemente in einem Baum zu
speichern.
Denke ich auch hinreichend bekannt aus Info 1.
Bäume sind auch sehr gut für Zugverfahren geeignet, weil ich durch
Bäume, wenn die geordnet sind, ein paar Mildenbedingungen
sicherstellen kann, dass ich immer logarithmische Laufzeit in der
Anzahl der Elemente habe.
Ist die linearverkettete Liste nur eine Richtung?
Die linearverkettete Liste ist nur eine Richtung.
Normalerweise vorwärts und die doppeltverkettete Liste ist in beide
Richtungen.
Was für Operationen gibt es denn typischerweise, die man auf solchen
Listen oder Arrays durchführt?
Zugriff auf einzelne Komponente.
Das heißt, ich möchte das ITE-Komponent, diese Liste oder Array von L,
auslesen.
Ich möchte einzelne Komponenten vergleichen.
Das sind typische Operationen, die durchgeführt werden.
Einmal zugreifen, einmal vergleichen.
Und die Kosten dieser Operationen, die ich habe, die hängen natürlich
von der gewählten Datenstruktur ab.
Im Array ist der Zugriff-Vergleich konstant, weil ich einen wahlfreien
Zugang habe.
Wovon eines?
Im Baum ist es logarithmisch.
Wohlgemerkt, die Elemente müssen schon angeordnet sein.
In einer verketteten Liste bin ich linear.
Warum?
Im mittleren Fall muss ich die Liste bis zur Hälfte traversieren.
Dann habe ich n halber Elemente traversiert.
Halber ist nur eine Konstante, das heißt, ich bin in der linearen
Laufzeitklasse.
Okay.
Wir steigen noch ein bisschen tiefer ein.
Wie sehen diese Probleme konkret aus?
Wir gehen jetzt immer davon aus, wir haben jetzt hier eine Liste der
Länge n.
Wir haben hier insgesamt n Elemente, S1 bis Sn.
Welche Probleme tauchen hierbei auf?
Wir sind vielleicht interessiert daran, das CAD-größte Element zu
berechnen.
CAD -größte Element, K von S, also K von K1 wäre dann das größte
Element und Kn wäre dann das kleinste Element.
Was z.B.
durch das K-größte Element, wenn man das Kn-halbte Element bestimmt,
dann hätte man den Media.
Z.B.
sehr interessant für statistische Analysen.
Klassiker ist natürlich Sortierproblem.
Ich kann entweder aufsteigen, sortieren oder fallen sortieren oder
absteigend oder aufsteigend sortieren.
Was ich auch noch machen möchte vielleicht, ich habe zwei sortierte
Teillisten und ich möchte die zusammenfügen, so genannter Merge.
Danach möchte ich natürlich sicherstellen, dass diese beiden
sortierten Listen, also das ist das Resultat der Verschmelzoperation,
dass es ebenfalls wieder eine sortierte Liste liefert.
Ich möchte eventuell herausfinden, ich habe ein Element und ich habe
eine Liste.
Ist denn dieses Element bereits in der Liste vorhanden?
Das ist die sogenannte Member-Operation.
Oder ich habe beispielsweise ein Element und ich möchte den Schlüssel
dafür herausfinden.
Also ich suche nach einem Element in der Liste und möchte den
zugehörigen Schlüssel dafür, den Vergleichsschlüssel, herausfinden.
Die sogenannte Search-Operation.
Eine andere Operation ist beispielsweise das Einfügen.
Ich möchte ein Element dieser Liste hinzufügen.
Elemente löschen.
Das kann man auch machen.
Oder, ja, das sind Einfügen, Löschen.
Das ist relativ einfach.
Aber was ist denn, wenn ich das kleinste Element einer Liste entfernen
möchte?
Ja, dann muss ich erstmal das kleinste Element bestimmen und danach
löschen.
Noch eine andere interessante Möglichkeit, was ich mit so einer Liste
machen kann, ich suche das nächstliegende Element in dieser Liste zu
einem bestimmten gegebenen Element A.
Das heißt, ich möchte das Element finden, das zu A am nächsten ist,
aber nicht im Sinne von der Listenposition, also nicht im Sinne des
Index, sondern im Wert.
Also wenn ich beispielsweise Zahlen habe, ich suche, ja, ich möchte in
der Liste die Zahl finden, die zu der Zahl 10 am nächsten ist.
Das wäre ein Beispiel, was hier durchaus gedrückt ist.
Aber natürlich, um sowas machen zu können, brauche ich eine
Distanzfunktion.
Für Zahlen, Buchstaben, Wörter kann man das noch sinnvoll definieren,
aber wenn man schon Records hat, dann wird es ein bisschen
schwieriger, eine Distanzfunktion festzulegen.
Aber das ist auch noch ein ganz interessanter Fakt, dass ungefähr ein
Drittel der Rechenzeit in kommerziellen Rechner nur für Aufgaben
dieser Art draufgeht.
Das heißt, das motiviert uns natürlich, da besonders effiziente
Verfahren zu finden, um diese einzelnen Operationen durchzuführen.
Okay.
Schauen wir uns mal diese eher komplexeren Operationen an.
Das heißt, wir haben Einfügen, Suchen und Löschen, sogenannte
Dictionary -Operationen.
Und wir haben einmal das Minimum, Suchen, Einfügen und Löschen.
Und da gefallen unter dem Begriff sogenannte Prioritätswarteschlangen,
weil das natürlich entscheidend ist, in welcher Reihenfolge ich die
durchführe.
Wenn ich zuerst ein Element hinzufüge und dann lösche, kann es sein,
dass ich das hinzugefügte Element schon gerade gelöscht habe.
Und wenn es sich vorher noch nicht in der Liste befand, dann läuft die
Löschoperation ins Leere.
Und wenn ich es danach hinzufüge, dann ist es wieder da.
Was verwenden wir für ein Komplexitätsmaß?
Also wie messen wir, mit wie viel Aufwand eine bestimmte Operation
verbunden ist?
Das ist die Anzahl der Vergleiche, die es durchführen muss für ein
bestimmtes Verfahren.
Und gerade bei Such- und Sortieroperationen ist es auch die Pfadlänge
im Entscheidungsbaum.
Das heißt, aber man muss natürlich beachten, Zugriff für die einzelnen
Komponenten.
Das heißt, wenn ich so einen Vergleich durchführen muss und mir dann
erstmal aus dem Hintergrundspeicher bestimmte Informationen holen
muss, und das je nach Art des Objektes mit unterschiedlichen Kosten
verbunden ist, das heißt, es kann sein, ich vergleiche zwar zwei
Objekte des gleichen Typs, aber es kann sein, dass der Zugriff auf die
Komponenten des einzelnen Typs, dass der mit unterschiedlichen Kosten
verbunden ist, ja, da muss ich das auch berücksichtigen.
Gerade bei sehr großen Datensätzen.
Allerdings, das betrachten wir hier an der Stelle nicht.
Wenn wir wieder von Parallelalgorithmen sprechen, dann ist das
Kostenmaß wie bisher die Anzahl der Schritte.
Das heißt, in einem Schritt werden dann mehrere Vergleichsoperationen
durchgeführt.
Und bei verteilten Algorithmen ist es wie bisher die Anzahl der
Nachrichten.
Okay, für Sortierverfahren, also wir betrachten jetzt zunächst mal
Sortierverfahren.
Die Annahme, die wir hierfür treffen, ist eine ganz entscheidende
zunächst.
Und zwar, abgesehen von der Ordnungsrelation, ist nichts über die
Elemente selbst bekannt.
Man nennt sowas auch allgemeines Sortierverfahren.
Der entscheidende Punkt ist dabei, ich kann die Eigenschaft der
Elemente nicht ausnutzen, um ein beschleunigtes Sortierverfahren zu
finden.
Wenn ich zum Beispiel weiß, dass die Elemente, die ich habe, dass die
sehr ähnlich sind, dann kann ich Algorithmen erzeugen, die das
ausnutzen und entsprechend schneller sortieren.
Also Stichwort BIM-Sort, falls es jemand schon mal gehört hat, werden
wir auch noch später besprechen.
Aber wichtig ist, das heißt, die Sortierverfahren, die wir zunächst
mal betrachten, die müssen für beliebige Elemente funktionieren.
Wichtig ist nur, da muss nur die Ordnungsrelation bekannt sein.
Aber die Eigenschaft der Elemente spielt keine Rolle.
Das heißt, wir gehen auch davon aus, dass die Liste als Array
realisiert ist.
Wir haben wahlfreien Zugriff.
Also uns entstehen keine Kosten dadurch, dass wir erstmal über eine
Liste iterieren müssen.
Das nehmen wir einfach an.
Und das ist eine bisschen vereinfachende Annahme, die dritte hier.
Aber sie erleichtert die Analyse.
Und zwar, wir gehen davon aus, dass die Elemente der Liste verschieden
sind.
Das heißt also, kein Element wird zweimal in der Liste abgespeichert.
Wir haben ja schon in Info 1 verschiedene Verfahren kennengelernt.
Die werden wir jetzt auch nochmal Schritt für Schritt durchgehen, aber
anhand von anderen Kriterien analysieren.
Das erste, was wir betrachten, ist Sortieren durch Auswahl, sogenannte
Selection Sort.
Wie gehe ich hier vor?
Ich iteriere einmal über die komplette unsortierte Liste drüber, von K
-1 bis N-1.
Dann bestimme ich immer das aktuelle Minimum dieser Restliste, also
des unsortierten Teils.
Und vertausche den aktuellen Index, an dem ich mich befinde, hier SK,
mit dem gefundenen Minimum.
Hierzu auch ein kurzes Beispiel.
Also ich starte hier an der Stelle 2, also hier Index K gleich 1.
Ich suche das aktuelle Minimum, das ist 1.
Dann vertausche ich die beiden.
Und hier findet eine Vertauschoperation statt.
In der nächsten Iteration beginne ich hier beim Index K gleich 2,
bestimme jedes Minimum, das ist jetzt 2, was ich gerade vorhin
rübergetauscht habe, und vertausche die beiden.
Ganz einfach.
Nächste Iteration wieder.
Ich bin hier bei 5.
3 ist das Minimum der Restliste.
Dann bin ich hier bei dem Index K gleich 4.
Mein Minimum befindet sich hier in der Restliste ganz am Ende, die
Nummer 4.
Dann wird das vertauscht.
Und am Ende muss ich hier nur noch 6 und 5 vertauschen.
Und ich bin am Ende angekommen.
Das heißt, ich bestimme immer das Indeminimum dieser Restliste und
füge das an meine aktuelle Position ein, wo ich mich befinde im
Schleifendurchlauf.
Das heißt, der Aufwand, der hier entsteht, ja, das ist ganz klar, N
mal, ich iteriere einmal über die komplette Liste drüber und ich muss
in jeder Iteration das Minimum bestimmen.
Das heißt, ich habe hier N mal für den Aufwand Bestimmung des
Minimums.
Okay.
Man kann sich überlegen, wie aufwendig ist es denn, das Minimum zu
bestimmen.
Dazu gibt es ein kleines Lemma.
Und zwar, jeder Algorithmus, der nur mit binären Vergleichen arbeitet,
braucht mindestens N-1 Vergleiche für die Bestimmung des Minimums oder
des Maximums.
Klar, ob ich jetzt das Minimum bestimme oder das Maximum, das ist das
Gleiche.
Okay, der Beweis, warum ist das denn so?
Ich meine, das ist eigentlich relativ intuitiv.
Man kann sich das so vorstellen, man hat einen Wettkampf zwischen N
-Spielern oder N-Teams, wie bald bei der Europameisterschaft im
Fußball.
Das heißt, das beste Team darf nie verlieren.
Ja, das ist bei der Europameisterschaft durch die Gruppenphase ein
bisschen anders, aber wenn man sich jetzt nur die Finals anschaut, das
heißt, ab dem Achtelfinale, dann darf ja kein Team verlieren.
Das heißt, nur das Team, das alle Finalspiele gewinnt, wird
Europameister.
Okay, das heißt, wenn der Beste nie verlieren darf, dann müssen die
anderen N-1 Spieler mindestens einmal verlieren.
Pro Spiel verliert genau ein Spieler, das heißt, es gibt mindestens N
-1 Spieler.
Gut, man kann sich das ja auch ungefähr so vorstellen.
Man hat hier die einzelnen Spieler, die treten jeweils gegeneinander
an.
Das heißt, der Gewinner von den beiden hier, der rückt weiter nach
vorne.
Der Gewinner von den beiden rückt auch weiter nach vorne und am Ende
werden die beiden miteinander verglichen.
Ganz einfach.
Okay, das heißt, wenn wir das sequentiell machen, ja, dann brauche ich
N -1 Vergleich, weil die Vergleiche unser Kostenmaß sind.
Das heißt, wenn ich immer N-1 vergleiche, benötige, um das Minimum zu
bestimmen, dann sind es im Schnitt, ja, sind es ein Halb von N-1, ja,
weil ich ja immer die durchschnittliche Länge der Liste habe,
beziehungsweise auch wenn ich alle Minima dieser Restliste bestimme,
ja, komme ich trotzdem hier auf einen quadratischen Aufwand.
Was relativ schlecht ist.
Genau, also das ist auch im Mittel nicht besser.
Das heißt, ja, es ist eigentlich kein so sonderlich gutes
Sortierverfahren.
Aber wir schauen uns ja auch hier parallele Algorithmen an und da ist
an der Stelle ja noch ein ganz interessanter Einschub.
Ich meine, natürlich kann man das parallel in Log-End-Schritten
bestimmen.
Das ergibt sich relativ intuitiv hier aus diesem Graphen hier und aus
dem Graphen, den ich hier gezeichnet habe, ja.
Das heißt, diese einzelnen Vergleiche hier auf der Ebene, die kann ich
ja immer parallel durchführen.
Und das heißt, ich habe hier einen Baum, wo sich die Anzahl der
Vergleiche pro Ebene immer halbiert und dadurch komme ich natürlich
auf logarithmische Laufzeit.
Allerdings kann man das auch noch verbessern und zwar durch einen
anderen Ansatz, wenn man insgesamt n² Prozessoren verwendet.
Okay, das heißt, wie gehen wir hier vor?
Wir haben n² Prozessoren und dann haben wir hier ein Array E.
Das ist folgendermaßen aufgebaut.
Das heißt, wir haben hier das erste Register, das ist dann später das
Ergebnisregister.
Wir schreiben erstmal 0 in alle Register rein.
Das heißt, wir schreiben hier in die alle erstmal zu Beginn 0 rein.
0, 0, 0, 0, 0.
Und dann wird folgender Vergleich durchgeführt.
Also wir haben hier zwei Indizes, i und j, die alle aus dem Bereich 1
bis n sind.
Und dann führe ich einen Vergleich durch.
Das heißt, der Prozessor PIIJ vergleicht das Element SI mit SJ unserer
Folge.
Und wenn jetzt SI größer ist als SJ, dann schreibe ich eine 1 an die
Position i in diesem Ergebnisarray.
Das heißt, wenn hier ein i ist und SI ist größer als SJ, dann schreibe
ich hier eine 1 rein.
Okay, als nächstes überprüfe ich oder schreibe.
Dann gehe ich folgendermaßen vor, also dann brauche ich nur noch einen
Endprozessor.
Das heißt, für Prozessor PII schreibt er den Index seines Elementes in
dieses Ergebnisarray hier rein, falls da noch eine 0 steht.
Okay, was passiert?
Wenn da jetzt eine 1 steht, dann gibt es auf jeden Fall ein Element.
Ja, dann ist es nicht das Minimum, weil dann ist SI größer als
irgendein anderes SJ.
Das heißt, wenn es kein Element gibt, das größer ist als SI, dann
steht da noch eine 0.
Und das heißt, am Ende wird hier in diesem kompletten Array, also
abgesehen von dem Index hier vorne 0, wird hier nur eine einzige
Speicherzelle den Wert 0 aufweisen.
Und dieser eine Prozessor schreibt dann seinen Index hier vorne rein.
Das heißt, hier sind insgesamt nur drei Schritte erforderlich, um den
Index des Minimums zu bestimmen.
Das heißt, allerdings erfordert diese Prozedur hier, sieht man ja
schon, also jeder Prozessor vergleicht jedes Element mit jedem anderen
Element, wir brauchen hier n²-Vergleiche.
Also relativ aufwendig.
Und das Weitere müssen wir auch gleichzeitig lesen, das heißt, wir
haben ja n Prozessoren, die jeweils das i-Element auslesen und n
Prozessoren, die jeweils das j-Element auslesen.
Das heißt, sie müssen gleichzeitig lesen können und sowie
gleichzeitiges konfliktfreies Schreiben.
Weil wir haben ja immer n Prozessoren, die gegebenenfalls auf so eine
Speicherzelle zugreifen wollen.
Also das größte Element zum Beispiel, da wird dann n-1 mal die 1
reingeschrieben in diese Speicherzelle.
Das heißt, um das auf die Konzepte runterzubrechen, die wir gelernt
haben, also wir brauchen PRAM, das heißt, wir müssen in der Lage sein,
gleichzeitig Elemente lesen zu können, dann concurrent read,
concurrent write.
Prozessoren dürfen gleichzeitig Elemente auslesen und auch
gleichzeitig schreiben und als Schreibregel wird eben die sogenannte
Common Schreibregel verwendet.
Das heißt, ein Wert wird immer nur in der Speicherzelle geschrieben,
wenn mehrere Prozessoren gleichzeitig schreiben wollen, wenn sie den
gleichen Wert schreiben.
Das heißt, wenn die unterschiedliche Werte schreiben wollen, dann darf
nicht geschrieben werden.
Wenn wir das Ganze in unsere Formel einsetzen, dann sehen wir ja,
Effizienz ist relativ gering.
Die ist nur 1 durch n.
Also wir haben relativ hohen Zeitgewinn, allerdings die Effizienz
dadurch, dass wir n² Prozessoren brauchen, die ist äußerst gering.
Das heißt, es ist kein sonderlich effizientes Verfahren.
Den nächsten Algorithmus, den wir betrachten, ist das Sortieren durch
Einfügen oder das Konzept, das dahinter steht, das Sortieren durch
Einfügen.
Der Algorithmus selbst, der nennt sich Insertion Sort.
Wie gehen wir vor?
Wir iterieren hier auch über dieses unsortierte Feld und wir
betrachten immer das aktuelle Element im Index und fügen das an der
korrekten Stelle ein, in der bereits sortierten Liste.
Was durch diesen Befehl hier dargestellt ist.
Auch hier ein kleines Beispiel.
Wir gehen davon aus, dass unsere unsortierte Liste ist S und die
sortierte Liste ist dann T.
Das heißt, wir lesen hier Schritt für Schritt die einzelnen Elemente
aus der unsortierten Liste ein.
Wir beginnen mit einer 2, die können wir direkt speichern.
Dann lesen wir als nächstes die 5 ein.
Die 5 ist bisher das größte Element in dieser sortierten Teilliste.
Dann müssen wir das ganz hinten einfügen.
Als nächstes die 1.
Die 1 ist das kleinste Element, die muss ganz vorne eingefügt werden.
Dann die 3.
Die 3 steht jetzt zwischen der 2 und der 5.
Da ist die 3.
Als nächstes die 6.
Und die 6 ist zu dem Zeitpunkt das größte Element.
Bleibt es auch später, wird ganz hinten eingefügt.
Und die 4 schließlich.
Wir drehen auch einmal drüber und sehen, die gehört zwischen die 3 und
die 5.
Auch ein relativ einfaches Verfahren.
Was für eine Analyse, also die Analyse, wie ist denn die Laufzeit
davon?
Im schlechtesten Fall müssen wir das neue einzufügende Element hier
immer an das Ende schreiben.
Immer an das Ende.
Was passiert dann, wenn wir es ans Ende schreiben, müssen wir einmal
über die komplette Liste durchgehen.
Also wir starten immer von links.
Schauen an welcher Position wird es eingefügt.
Das heißt, wir gehen einmal drüber und dann haben wir hier diese
Summe.
Am Anfang haben wir 1, dann in der zweiten Iteration 2, in der dritten
3 und immer so weiter.
Also wir haben hier die Gauss'sche Summe.
Und es ist ja bekanntlich, wenn man das hier auflöst, es ist ja 1 halb
n mal n plus 1.
Und ja, das ist eine quadratische Laufzeit.
Das heißt, im schlechtesten Fall stehen wir ziemlich schlecht da.
Ja, im Mittel müssen wir immer bis zur Mitte der Liste gehen.
Das heißt, statt I steht dann hier I halber.
Ja, aber auch das, wenn wir das wieder ausrechnen, okay, dann haben
wir halt ein Viertel n mal n plus 1.
Ja, die sind immer noch quadratisch.
Das heißt, auch im mittleren Laufzeitverhalten ist das relativ
schlecht.
Allerdings im besten Fall, das ist zum Beispiel, wenn jetzt hier die
Liste schon absteigend sortiert wäre, dann würde ich ja jedes neue
Element wieder an den Listenanfang einfügen.
Ja, dann hätte ich insgesamt nur n Vergleiche.
Das heißt, im besten Fall bin ich ja linear und das ist schon mal
ziemlich gut.
Okay, dann schauen wir uns auch noch Bubble Sort an.
Das dürfte auch noch gut bekannt sein aus Info 1.
Das läuft folgendermaßen ab.
Ich iteriere hier wieder über mein unsortiertes Feld.
Und dann habe ich noch eine innere Schleife, die einmal von dem
letzten Element bis zu meinem aktuellen Schleifenindex K iteriert.
Und das läuft dann folgendermaßen ab.
Das heißt, ich betrachte immer die zwei direkten Nachbarn.
Und wenn sich jetzt quasi die Nachbarn an der falschen Stelle
befinden, das heißt, wenn das Vorgängerelement größer ist als das
Nachfolgerelement, was hier der Fall ist, dann führe ich eine
Vertauschoperation durch.
Und hierzu auch noch ein Beispiel.
Ich beginne hier unten, also K ist zuerst gleich 2.
Ich fange hier unten an.
Ich sehe, dass 6 und 4, also hier ist der erste Tausch, den ich
durchführe.
Ich sehe, 6 ist größer als die 4.
Das heißt, ich muss hier einen Tausch durchführen.
Dann betrachte ich als nächstes 4 und 3, die sind an der richtigen
Stelle.
1 und 3 auch, 1 ist kleiner als die 3.
Dann schaue ich mir hier die 5 und die 1 an.
Ich sehe, ok, 5 ist größer als die 1.
Die muss auch nach unten sickern.
Im nächsten Schritt schaue ich mir die 1 und die 2 an.
Ich sehe, ok, die 2 ist größer als die 1.
Ich muss hier vertauschen.
Nach der ersten Iteration habe ich ja schon sichergestellt, dass das
kleinste Element sich ganz oben an der Liste befindet.
Das heißt, ich muss in der nächsten Iteration nur noch hierzu bis S2
durchiterieren.
Ich fange auch wieder unten an, 6, 4, 3, das ist alles schon mal
richtig.
Haben wir hier 3 und 5, müssen miteinander vertauscht werden.
Gehe ich dann nach oben, 2 und 3 sind schon richtig.
Ich kann hier terminieren.
Und dann muss ich noch einen Vergleich durchführen.
In der nächsten Iteration, hier 4, 5, befinden sich an der falschen
Stelle.
Wird vertauscht.
Ich bin bei 3 angekommen und am Ende sehe ich schon, hier, die Liste
ist korrekt sortiert.
Ich kann terminieren.
Im Bubble Sort kommt der Name... Frage dazu, ja?
Die Spalte, das heißt, an der Stelle habe ich 4 und die 5 vertauscht.
Das heißt, ich bin dann bis hier fertig.
Ich muss quasi noch einmal drüber gehen, um sicherzustellen, dass
wirklich alles richtig ist.
Das heißt, erst nach der Iteration habe ich ja keinen Tausch mehr
durchgeführt hier.
Und deshalb weiß ich, ich muss keinen Tausch mehr durchführen.
Also hier bin ich sogar am Ende der Iteration angekommen.
Also Bubble kommt daher, man vergleicht es so mit Blasen.
Die leichten Elemente steigen nach oben und die schweren nach unten.
Deshalb ist das Ganze hier auch senkrecht angeordnet und nicht
waagrecht.
Hier nochmal eine kurze Laufzeitanalyse.
Wenn ich das nach dieser Variante, also nach dem Code, so wie er hier
dasteht, mache, dann habe ich immer n mal n-1 halbe Vergleiche.
Das heißt, ich liege immer in der quadratischen Laufzeit.
Unabhängig davon, wie meine Daten vorliegen.
Ob die schon vorsortiert sind oder ob die irgendwelche anderen
Eigenschaften haben, die bei anderen Algorithmen zum Beispiel eine
Verbesserung der Laufzeit bewirken.
Es sind allerdings geringfügige Verbesserungen möglich.
Und zwar kann ich ja auffallen, wenn ich nicht mehr vertauscht werde.
Das heißt, ich muss mir einfach nur merken, irgendwie so eine Flag
setzen.
Okay, wurde denn in der Iteration ein Tausch durchgeführt?
Wenn nicht, kann ich schon relativ schnell terminieren.
Wenn die Liste vorsortiert ist, gehe ich nur einmal drüber, dann wäre
ich linear.
Das wäre gut.
Was ich auch noch machen kann, ist, ich sortiere abwechselnd von links
nach rechts, beziehungsweise von oben nach unten und von unten nach
oben.
Dieses Verfahren nennt sich dann Shaker Sort.
Allerdings noch eine Anmerkung dazu, auch das führt im Mittel
allerdings nicht zu einer Verbesserung der Laufzeit.
Okay, jetzt schauen wir uns aber mal eine parallele Variante von
Bubble Sort an, und zwar das sogenannte Odd-Even Transposition Sort.
Das heißt, wir haben hier ein lineares Prozessorfeld mit einem
Prozessor.
Und wir führen auch hier immer Vergleiche paarweise durch.
Also wir iterieren hier auch einmal von i bis n, einmal über die Länge
dieses Arrays durch.
Und dann habe ich hier noch eine innere Schleife, wo ich parallel
diese Vergleiche durchführe.
Das heißt, abgesehen von dem Index, an dem ich mich gerade finde,
führe ich entweder einen Odd- oder einen Even-Schritt durch.
Also hier die Prüfung.
Das heißt, ich vergleiche immer die Nachbarn miteinander und
vertausche die gegebenenfalls.
Das ist dieses Comparison Exchange, was hier steht.
Und ich beginne mit einem ungeraden Index, dann mache ich weiter mit
einem geraden Index, also der nächsten Iteration.
Okay.
Das heißt, im Endeffekt, was ich hier mache, das ist nur Bubble Sort
und die Vergleiche gleichzeitig durchgeführt.
Ich male es auch nochmal ganz kurz an, damit es ein bisschen
verständlicher wird.
Also ich habe hier ein Array.
Wenn ich einen Odd-Schritt habe, dann vergleiche ich jeweils immer die
Elemente und vertausche die eventuell.
Und wenn ich einen, mache ich mal hier noch eine Zelle dazu.
Die hier und in einem... also das ist Odd.
Wenn wir mal gucken, damit es ein bisschen vernünftiger wird, wechseln
wir noch die Farbe.
Und in einem Even-Schritt vergleichen wir entsprechend die geraden
Indizes miteinander.
Okay.
Und wieder zurück zu Odd.
Okay.
Gehen wir mal den Algorithmus Schritt für Schritt durch und überlegen
uns die Laufzeit.
Okay, wir haben hier die äußere Schleife, das sind insgesamt n Mal
wird die durchlaufen.
Und das hier innen wird parallel gemacht.
Das ist immer quasi ein konstanter Aufwand bezogen auf einen Durchlauf
der äußeren Schleife.
Das heißt, wir haben doch hier eine Laufzeit von n, lineare Laufzeit.
Der Parallelitätsgrad, der ist nur ein halber, weil jeweils immer nur
ein halber Prozessor beteiligt ist.
Also wenn hier so ein Vergleichschritt durchgeführt wird, hier oben,
dann ist es so, dass sich quasi dieser Prozessor hier, der holt sich
das Element von seinem linken Nachbarn und vergleicht es mit seinem
eigenen und führt es eventuell durch.
Das heißt, es ist eigentlich immer nur ein Prozessor beteiligt, der
wirklich rechnet, der einen Vergleich durchführt.
Das heißt, dann schauen wir uns mal den Zeitgewinn an.
Zeitgewinn war ja bester lineare Algorithmus durch Laufzeit des
parallelen Verfahrens.
Also wir haben hier dann bestes sequenzielles Verfahren, ist n log n.
Geteilt durch n haben wir einen Zeitgewinn von Logarithmus von n,
relativ gering.
Und eine Effizienz, da teilen wir den Zeitgewinn nochmal durch die
Anzahl der Prozessoren, die beteiligt sind.
Und wir haben dann log von n geteilt durch n.
Das heißt eigentlich auch eine relativ schlechte Effizienz.
Okay, aber warum betrachten wir das dann?
Ja, es ist so, dass wenn wir ein lineares Feld haben mit n
Prozessoren, also wie hier oben angegeben, dann geht es einfach nicht
besser.
Also das ist das beste Sortierverfahren auf einem linearen
Prozessorfeld mit n Prozessoren.
Deshalb wird odd-even-transposition-sort auch bei vielen
Sortierverfahren auf linearen Prozessorfeldern irgendwie als
Subroutine eingesetzt.
Das heißt, man kann ja auf linearen Prozessorfeldern, also in n kreuz
n Prozessorfeldern, und man möchte das zum Beispiel in Schlangenlinien
sortieren oder irgendeiner Art und Weise sortieren.
Da wird sehr häufig mit odd-even-transposition-sort irgendwie als
Subroutine verwendet, um jetzt einzelne Zeilen oder Spalten zu
verwenden, weil es eben optimal ist für lineare Felder mit n
Prozessoren.
Der Grund, warum es nicht besser geht, wenn wir auf linearen Feldern
sortieren, ist, im schlimmsten Fall müssen ja P1 und Pn ihre Daten
vertauschen.
Das heißt, das kleinste Element muss einmal von links nach rechts
wandern und das größte einmal von rechts nach links.
Und das erfordert eben n Vergleiche.
Man kann sich das intuitiv überlegen, odd-even-transposition-sort wird
schon richtig sortieren, aber man kann sich natürlich auch überlegen,
das kann man doch auch irgendwie beweisen, oder?
Und dazu führen wir folgenden Beweis durch.
Also die Behauptung ist, nach n odd- bzw.
n even-Schritten ist die Folge sortiert, ebenso nach n even-odd
-Schritten.
Das heißt, unabhängig davon, ob ich zuerst mit einem odd-Schritt
anfange oder mit einem even-Schritt.
Also ob ich zuerst mit einem Comparison-Exchange mit den ungeraden
Indizes initiiere oder mit den geraden.
Das beweise ich per Induktion für ein Feld der Länge n.
n gleich 1?
Trivial, ja.
Ich habe ein Element, das ist immer schon sortiert.
n gleich 2?
Ja, auch relativ offensichtlich.
Also entweder ein odd- oder ein even-Schritt reichen immer aus.
Ein Comparison-Exchange zwischen diesen beiden Elementen und schon
habe ich die Folge sortiert.
Okay, was passiert denn jetzt?
Ja, ich mache einen Induktionsschritt, also von n auf n plus 1 gehe.
Was ich hier mache, ich betrachte jetzt also den Weg des maximalen
Datums, den Weg, den das Maximum zurücklegt in einem linearen Feld der
Länge n.
Und zwar in einem sogenannten Raum-Zeit-Diagramm.
Dieses Raum-Zeit-Diagramm kann man auch als Vergleichernetz
darstellen.
Also ein Raum-Zeit-Diagramm projiziert gewissermaßen diese ganzen
Vergleiche, die hier stattfinden.
Also die finden ja immer Linearschritte auf dem Prozessorfeld, also
zeitlich.
Wir fügen hier eine zusätzliche Achse hinzu, die die Zeit darstellt.
Und das Ganze kann man eben auch durch ein Vergleichernetz machen.
Das wäre dann eben entsprechend die Hardware-Realisierung.
Das heißt, ich habe Eingänge, an denen die einzelnen Elemente
runterkommen, was hier dargestellt ist.
Also hier S1 bis S8.
Und das heißt, diese Elemente, die kommen hier unten.
Das sind hier so Leiterbahnen, die man sieht.
Und wenn immer hier so ein Pfeil dasteht, wird dann ein Vergleich
durchgeführt.
Und entsprechend, gegebenenfalls, werden diese beiden Elemente
vertauscht, die da angegeben sind.
Okay, wenn wir uns jetzt das maximale Element anschauen, nehmen wir
an, das ist jetzt S1.
Also S1 ist unser maximales Element.
Wenn wir das sortieren, und am Ende soll dann, ja, es wird aufsteigen
sortiert, dann muss S1 ja die Position von S8 einnehmen.
Und das heißt, den Weg, den dieses S1 im Raum-Zeit-Diagramm
zurücklegt, entspricht gerade diesem Weg, der hier angegeben ist.
S1 wird zuerst mit S2 verglichen, dann mit S3, bzw.
das Element, das sich dann an der Stelle S3 befindet, usw.
Und ja, wir sehen, wenn wir hier eine Liste der Länge n haben, dass ja
maximal n plus 1 Schritte ausreichen, bis das Maximum seinen Platz
erreicht hat.
Das heißt, Folge der Länge n plus 1, maximal n plus 1 Schritte.
Okay, das ist schon mal gut.
Dann überlegen wir uns, okay, also wir machen den Induktionsschritt
gewissermaßen rückwärts.
Was passiert denn, wenn ich dieses maximale Element eliminiere, oder
den Weg, den das zurücklegt, in diesem Vergleichernetz?
Okay, was dann passiert?
Das fällt alles weg.
Das heißt, alle Vergleiche mit diesem Maximum fallen weg.
Das heißt, höchstens ein Vergleich pro parallelem Schritt.
Also die Vergleiche, die ich mit S1 durchführe, die fallen weg.
Das heißt, ein Schritt pro parallelem Vergleichsschritt fällt weg.
Allerdings, alle übrigen Vergleiche werden ja trotzdem durchgeführt.
Diese werden ja nicht beeinflusst von diesem einzelnen Element.
Das heißt, die weiteren Odd-Even-Schritte werden nach wie vor
durchgeführt.
Die Nachbarn werden nach wie vor miteinander verglichen und
gegebenenfalls vertauscht.
Wenn ich das jetzt nochmal ganz genau betrachte und im Endeffekt diese
ganzen Vergleiche, die hier passieren, so nach links schiebe, dann
fällt mir auf, das sind ja genau die Vergleiche, die OETS auf eine
Folge der Länge N mit N Odd-Even-Schritte durchführt.
Und das heißt, nach Induktionsannahme, unsere Annahme sagt ja, OETS
sortiert korrekt eine Folge der Länge N in N Schritten.
Nach Induktionsannahme ist das erfüllt.
Und dadurch wird auch die gesamte Liste in N plus 1 Schritten
sortiert.
Und das ist schon das Ende des Beweises.
Okay, dann machen wir noch mit dem nächsten Konzept zur Sortierung
weiter, und zwar sortieren durch Teilen, der sogenannte Quicksort
-Algorithmus.
Und zwar dieser verwendet das Prinzip Divide and Conquer.
Also wir sehen schon wieder Divide and Conquer, das sind doch
Rekkurrenzgleichungen, ja, das ist uns schon mal begegnet.
Also Rekkurrenzgleichungen begegnen uns immer wieder.
Wie geht Quicksort vor?
Okay, ich wähle ein beliebiges Element von S, C, das sogenannte Pivot
-Element.
Wir nehmen mal hier an, das ist das erste Element der Liste.
Ich kann auch ein ganz anderes wählen.
Und dann führe ich folgende Prozedur durch.
Das heißt, ich zerteile meine Folge S in zwei Teilfolgen, S1 und S2',
sodass sich alle Elemente, die sich in S' befinden, kleiner gleich
diesen Pivot-Element sind.
Und alle Elemente, die größer sind als das Pivot-Element, die befinden
sich hier in der zweiten Hälfte.
Also eben, das ist S' und das hier ist S2'.
Okay.
Als nächstes wende ich genau dieses Verfahren wieder rekursiv auf die
einzelnen Teillisten an.
Das heißt, hier und hier wende ich rekursiv dieses Verfahren an.
Das heißt, ich fange wieder bei 1 an und arbeite Schritt für Schritt
durch, solange bis ich auf eine Folge der Länge 1 komme.
Okay, dann analysieren wir mal diesen Algorithmus.
Wie kann ich denn diese Aufteilung durchführen?
Also, dass ich dann Elemente habe, die entsprechend... dass diese
Aufteilung korrekt ist, dass wirklich Elemente, die kleiner gleich
sind als C in S' sind und die, die größer sind als C in S2'.
Ja, das kann ich einfach realisieren, indem ich zwei gegeneinander
linear verschobene Zeiger habe.
Das heißt, ich gehe hier von links nach rechts drüber, schaue mir an,
okay, ist dieses Element, das ich hier finde...
also, ist das größer als C?
Auf der anderen Seite finde ich eines, das ist kleiner als C, dann
vertausche ich die beiden.
Also, ich finde hier einfach ein Element, das ist kleiner gleich C und
da drüben finde ich eins, das ist größer, dann vertausche ich das.
Wenn ich das so durchführe, dann kreuzen sich diese Zeiger irgendwann
mal.
Und an dem Punkt, wo sie sich kreuzen, da ist dann das Pivot-Element
und dadurch habe ich dann diese zwei vorsortierten Teilfolgen.
Sehr leicht realisierbar und vor allem in linearer Zeit machbar.
Ich muss hier lediglich, ja, mich quasi bis zur Mitte der Folge oder
im schlimmsten Fall einmal über die komplette Folge durch mit beiden
Zeigern, aber wäre auch noch 2n.
Kein Problem, lineare Aufwand.
Okay, wie setze ich denn jetzt die Zeitkomplexität dann insgesamt
zusammen, wenn ich hier eine Rekurrenzgleichung aufstelle, also T von
Quicksort.
Okay, das ist einmal den Aufwand, den ich habe, um die linke Teilfolge
zu sortieren.
Also das hier ist links.
Plus den Aufwand, den ich für die rechte Teilfolge habe.
Und natürlich noch den linearen Aufwand, wie in Schritt 2 gesehen.
Okay, was passiert denn im schlechtesten Fall?
Im schlechtesten Fall verringert sich, ist es so, dass ich eine
Teilfolge der Länge 1 habe und die andere Teilfolge hat die Größe n-1,
im schlimmsten Fall.
Das heißt, das Problem verringert sich immer nur um 1, das ich hier
löse.
Das heißt, wenn das der Fall ist, dann habe ich ja im Endeffekt n-mal
diesen Aufwand pro Ebene, den ich hier durchführen muss.
Das heißt, ich bin im schlechtesten Fall quadratisch.
Was auch schon mal für uns sehr schlecht ist.
Im besten Fall allerdings haben diese beiden Teillisten immer die
exakt gleiche Größe.
Also man sieht es hier im Endeffekt.
Was hier passiert ist, die Größe von S1 und die Größe von S2, die ist
identisch.
Kann auch hier nochmal ein kleines Schaubild.
Also der schlechteste Fall, das wäre dann, dass sich im Endeffekt das
immer nur so verringert um 1.
Das heißt, im besten Fall habe ich 2-mal T von n-halbe plus O von n.
Wenn ich das auflöse, ganz einfach mit der Mastertheorie, komme ich
auf eine Laufzeit n log n.
Was schon mal sehr gut ist für ein Sortierverfahren.
Was passiert denn im mittleren Verhalten?
Okay.
Also das mittlere Laufzeitverhalten von QuickSort.
Wir definieren hier einmal Vj.
Das ist die mittlere Anzahl von Vergleichen bei einem Aufruf von
QuickSort auf Teillisten der Länge j.
Also V steht für Vergleiche, die Anzahl der Vergleiche beim Aufruf auf
eine Liste der Länge j.
Okay.
Bei dem mittleren Verhalten müssen wir davon ausgehen, dass alle
Listenlängen im Endeffekt gleichwahrscheinlich sind.
Wenn alle Listenlängen gleichwahrscheinlich sind, dann müssen wir
einfach einen Erwartungswert bilden.
Okay, nochmal die Betrachtung.
Okay, der Fall V gleich 1.
Ich habe ein Element, Triviale, schon vorsortiert.
Genau das gleiche.
Wenn ich kein Element habe, dann muss ich gar nichts sortieren.
Was passiert, wenn ich n Elemente habe?
Ich bilde hier diesen Erwartungswert, den wir als Erwartungswert
nennen.
Und das ist quasi die Summe aller... das sind hier alle Szenarien, die
abgebildet werden.
Unabhängig davon, wie die Aufteilung stattfindet, also wie groß die
Listen sind, habe ich immer hier einen Aufwand von n plus 1 für die
Zeiger.
Also das ist der Aufwand für die Zeiger.
Okay, das hier ist dann der Aufwand für die linke Teilliste.
Und das hier ist der Aufwand für die rechte Teilliste.
Okay, ganz einfach.
Einfach nur aufgeschrieben.
Gut, das kann ich allerdings zusammenfassen.
Na klar, diese n plus 1, die kann ich ja rausziehen.
Wenn ich das n mal aufsummiere, dann habe ich hier n mal n plus 1.
Das teile ich gleich wieder durch n.
Okay, dann steht da natürlich n plus 1.
Und ich nehme auch mal hier eine andere Farbe.
Das heißt, das hier kommt zu dem hier.
Okay, und diese beiden hier, die kann ich ja einfach zusammenfassen im
Endeffekt, weil die ja symmetrisch sind.
Das heißt, wenn ich hier i gleich 1 einsetze, habe ich hier v von 0.
Und wenn i gleich n ist, habe ich hier auch v von 0.
Das heißt, hier zähle ich einfach nur einmal von 0 bis n oder bis n
minus 1 nach oben.
Und hier zähle ich von n minus 1 bis 0.
Okay, das heißt eigentlich ja, die sind symmetrisch, die kann ich
gerade zusammenfassen.
Das heißt, die beiden hier kann ich zusammenfassen.
Das ist einfach nur zweimal, wie wenn ich hier v von i verwende.
Entsprechend hier zweimal.
Und ab dem Index, den kann ich auch noch rausziehen.
Also ich fange an bei 0 zu zählen und zähle nur bis n minus 1.
Okay, was machen wir als nächstes?
Wir schauen uns einfach mal diesen Ausdruck an hier.
Also n plus 1 mal v von n plus 1 minus n mal v von n.
Das ist jetzt ein bisschen aus der Luft gegriffen, aber wir werden
gleich sehen, wenn wir das hier umformen, anhand des Ergebnisses, das
wir hier haben, dann kommen wir auf eine sehr schöne Rekursionsformel,
die wir dann auflösen können.
Und zwar, okay, wir setzen die Ergebnisse von hier oben, setzen wir da
unten ein.
Gut, das heißt, dieser Teil hier, minus n mal v von n, ja, das können
wir hier gerade einsetzen, v von n.
Das ist ja, im Endeffekt das hier ist ja v von n.
Ja, und der Rest hier ist v von n plus 1.
Von n plus 1 entsprechend, also nur der Teil hier, die n plus 1, die
kommen ja von hier vorne durch, von hier vorne.
Okay, das ist einfach nur in die Formel, statt n, n plus 1 eingesetzt,
dann kommen wir einfacher, kommen wir direkt auf den Eindruck.
Dann haben wir hier n plus 1 plus 1, hier oben entsprechend, der
Zellindex verschiebt sich auch um 1.
Ja, das war's schon.
Das hier kann man noch entsprechend auflösen, zusammenfassen, dann
kommen wir auf den Ausdruck drauf.
Okay, ein bisschen drüber gemalt, aber das hier im Endeffekt kann man
jetzt auch alles zusammenfassen.
Das heißt, diese beiden, ich wechsle noch mal kurz die Farbe, damit
man was erkennen kann.
Nehmen wir mal blau.
Das heißt, diese beiden Terme hier, die löschen sich ja fast
gegenseitig aus.
Die sind ja fast identisch, nur dass hier der Zellindex bis n minus 1
geht und hier bis n.
Das heißt, wenn ich das zusammenfasse, bleibt hier als Resultat nur
noch 2Vn durch.
Wenn ich jetzt n plus 1 mal n plus 2 minus n mal n minus 1 nehme, dann
kommt das hier raus.
Ich markiere es auch noch mal in einer anderen Farbe, damit man es
besser sieht.
Also wenn ich das hier mit dem hier zusammenfasse, dann kommt das hier
raus.
Okay, das habe ich sehr viel markiert, man sieht kaum noch was.
Aber wir haben ein sehr schönes Ergebnis, denn das kann ich jetzt
wieder umstellen und zusammenfassen.
Das heißt, ich löse hier die rechte Seite nach Vn plus 1 auf, dass ich
auf der linken Seite nur Vn plus 1 habe.
Das heißt, ich subtrahiere hier von der rechten Seite, oder ich füge
hinzu, ich addiere n mal Vn.
Und das Ganze zeige ich dann plus n minus n plus 1 und komme
entsprechend auf den Ausdruck hier.
Das ist ja schon eine sehr schöne Rekursionsgleichung, die ich
allerdings leider nicht mit dem Mastertheorem auflösen kann.
Allerdings kann ich diese Rekursionsgleichung trotzdem mit ein paar
anderen Tricks und Kniffen lösen.
Erstmal muss ich per Induktion zeigen, dass ich diesen Ausdruck hier
von der rekursiven Schreibweise auf die direkte Schreibweise
überführe.
Das ist ein bisschen aufwendig, machen wir nicht an der Stelle.
Aber was wir trotzdem noch zeigen sollten, ist, dass dieser Ausdruck
hier in O von n log n liegt.
Wir machen das, wir schauen uns hier dieses Integral an.
Also, es ist ja bekannt, dass das Integral von i bis i plus 1 von 1
durch x kleiner gleich 1 durch i ist.
Und 1 durch i ist wiederum kleiner als das Integral von i minus 1 bis
i von 1 durch x.
Warum ist das so?
Man kann sich das relativ gut vergegenwärtigen.
Also, dieses Integral hier ist ja im Endeffekt das hier.
Dann nochmal Zeigerfarben wechseln.
Dieses Integral hier ist ja das hier.
Und dieser Ausdruck hier, 1 durch i, das ist ja im Endeffekt das hier.
Also, wenn ich 1 durch i mal 1 nehme, dann habe ich genau diese
Fläche, die hier eingezeichnet ist.
Okay, dann wissen wir, okay, diese Abschätzung, die stimmt.
Das heißt, ich kann das Ganze auch noch aufsummieren.
Das heißt, wenn ich hier entsprechend diese einzelnen Teilglieder
aufsummiere, bleibt ja diese Relation hier erhalten.
Das heißt, die Summe von i gleich 2 bis n von 1 durch i, die kann ich
durch das Integral hier abschätzen, das auf der rechten Seite.
Integrale sind ja additiv.
Das heißt, ich kann diese Grenzen einfach zusammenfassen, habe hier
das Integral insgesamt.
Und wenn ich das hier auflöse, komme ich auf den Ausdruck.
Da ist eine obere Schranke für das hier, und das ist log von n.
Dann habe ich hier was stehen, 2 von n plus 1 mal Logarithmus von n.
Ja, und klar, das liegt in n log n.
Okay, und damit wäre das Ganze schon bewiesen.
Okay, wir haben ja schon gesehen, dass Quicksort Schwachstellen hat,
und zwar, ja, eines vor allem die Wahl des Pivot-Elements.
Das ist ein ganz großes Problem.
Man könne das verbessern.
Man könne beispielsweise immer das mittlere Element wählen.
Also, wenn ich hier gerade die aktuelle linke und rechte Schranke
habe, von der Teilfolge, die ich betrachte, könne ich einfach die
Mitte nehmen.
Vielleicht besser, aber im schlechtesten Fall, ja, bin ich immer noch
quadratischer.
Können Sie sich ja mal eine Folge überlegen, bei dem das genau der
Fall ist.
Ich nehme immer das mittlere Element und habe dann...
Nehmen Sie immer das mittlere Element.
Und je nachdem, wie die Elemente angeordnet sind, habe ich eine
quadratische Laufzeit.
Können Sie sich mal überlegen.
Würde auch eine schöne Übungs- oder Klausuraufgabe abgeben.
Und selbst im besten Fall, also der allerbeste Fall, den ich erreichen
kann, ja, ist immer n log n.
Ist gut, aber andere Sortierverfahren, die wir ja gesehen haben, die
erreichen trotzdem lineare Laufzeiten.
Man sieht ja schon relativ schön, es gibt kein perfektes, optimales
Sortierverfahren.
Dieses Sortieren durch Einfügen und optimiertes Bubble Sort, die
können natürlich lineare Laufzeiten erreichen, sind aber in der Regel
halt schlechter als Quick Sort, als Verfahren, die normalerweise n log
n erreichen.
Das heißt, man sollte vielleicht auch sein Sortierverfahren, das man
wählt, auch immer anhand der Daten auswählen, die dem zugrunde liegen.
Wenn ich weiß, dass die Daten schon vorsortiert sind, macht es
eventuell Sinn, auf so ein einfaches Verfahren zurückzugreifen, wie
Bubble Sort.
Was man natürlich auch machen könnte, man wählt ein zufälliges Element
aus der Liste aus, dann hätte ich so eine Art randomisiertes Quick
Sort, dann hätte ich im Erwartungswert, würde ich zwar auf n log n
kommen, aber es kann trotzdem sein, dass ich noch immer in den
schlechtesten Fall reinrutsche und ich habe natürlich einen
Zusatzaufwand für die Zufallszahlgenerierung.
Dann ein weiteres Verfahren, also eine strikte Anwendung von den
beiden Conquer.
Quick Sort verwendet schon die beiden Conquer, aber die Aufteilung und
die Teilprobleme sind nicht immer exakt gleich.
Wenn ich die Aufteilung und die Teilprobleme, also die relative Größe
zum Ursprungsproblem, wenn die immer exakt gleich ist, dann möchte ich
das sogenannte Merge Sort Verfahren.
Wie gehe ich hier vor?
Ich teile zwei Listen, also ich habe die Liste S, ich teile sie in
gleich große Listen, S' und S'', und dann wende ich wieder rekursiv
Merge Sort auf diese beiden Teillisten an.
Und dann verschmelze ich diese beiden Listen, also ich wende es
rekursiv an, als Resultat bekomme ich dann sortierte Teillisten und
diese Teillisten verschmelze ich dann schließlich.
Als Beispiel, wie sieht es aus?
Also ich habe hier, ich führe die erste Teilung durch, dann teile ich
weiter, das heißt, diese Teilliste hier, die wird nochmal geteilt und
diese wird nochmal geteilt und entsprechend geht es weiter auf
einelementige Listen runter und die füge ich dann zusammen und
sortiere die gleich.
Das heißt, hier 2,3 ist schon sortiert, 5,1 wird in 1,5 sortiert, 7,8
ist schon richtig und 4,6 hier muss entsprechend getauscht werden.
Diese beiden sortierten Listen füge ich auch zusammen, 2,3,1,5 zu 1,2
,3,5 und 4,6,7,8 und schließlich, wie ich es gesagt habe, diese Liste
wieder zusammen zu einer sortierten Liste.
Das ist natürlich wie, hier werden die Listen vollständig gleichmäßig
aufgeteilt, die haben immer die gleichen Teilgrößen und ich habe
natürlich immer Log2n-Merge-Stufen, weil ich immer gleich groß
aufteile und wenn man den Aufwand betrachtet, dann sehen wir hier, wir
teilen immer gleichmäßig auf, das heißt, wir haben immer 2
Teilprobleme, die immer die halbe Größe haben des Ursprungsproblems
und der Aufwand, um 2 sortierte Teillisten zusammenzufügen, ja, der
liegt in N.
Kann man sich auch ganz einfach überlegen, ich kann ja hier
beispielsweise 2 gegeneinander verschobene Zeiger bilden und dann von
links und von rechts durchgehen und dann immer schauen, ok, dann nehme
ich immer zuerst das kleinere Element, der einen Liste, erhöhe den
Zeiger und mache das so in G-Schritt-Weise.
Also ich füge quasi immer das Minimum der jeweiligen, der beiden
Listen ein, in diese kombinierte Liste und erhöhe dann immer nur den
Zählindex in der Liste, aus der ich das Element genommen habe, das ich
gerade eingefügt habe.
Das ist genau die gleiche Rekursionsformel für Quicksort im optimalen
Fall, das heißt, ich komme auf N-Log-N-Schritte und noch ganz kurz zum
Abschließen, so, wenn ich jetzt das Ganze parallel mache, ja, dann ist
dieser Schritt hier das, wo ich sequenziell 2 Teilprobleme abarbeiten
müsste, das kann ich parallel machen.
Und ja, die Frage ist natürlich, ok, kann ich den auch parallel
merchen?
Ist das möglich?
Wenn ich es schaffe, dieses Merchen in logarithmischer Laufzeit
durchzuführen, dann ist die gesamte Laufzeit, also des parallelen
Merchsorts, die schaffe ich dann in quadratisch-logarithmischer
Laufzeit.
Und wie das Ganze dann funktioniert, das schauen wir uns nächste Woche an.