Übung 4 (Verkettung von Sortierern und Comparator)

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Max_S
Erstie
Erstie
Beiträge: 14
Registriert: 16. Apr 2015 17:09

Übung 4 (Verkettung von Sortierern und Comparator)

Beitrag von Max_S » 26. Jun 2016 11:32

Hallo,
wie genau läuft denn diese Verkettung ab? In der Sprechstunde hab ich das soweit verstanden, dass man die Komplexitätsklasse des jeweiligen Sortierers mit der Komplexitätsklasse des Comparators multipliziert ohne n zu "überladen".

Ich geb mal ein Beispiel: Nehmen wir an unser Comparator hat die Komplexitätsklasse Theta(n^2). Bubble Sort hat im Worst-Case O(n^2) und im Best Case O(n).

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 4 (Verkettung von Sortierern und Comparator)

Beitrag von Prof. Karsten Weihe » 26. Jun 2016 16:46

Max_S hat geschrieben: Ich geb mal ein Beispiel: Nehmen wir an unser Comparator hat die Komplexitätsklasse Theta(n^2). Bubble Sort hat im Worst-Case O(n^2) und im Best Case O(n).
Bubblesort hat im Worst Case und auch im Best Case Komplexität \(\Theta(n^2)\), oder? Es sei denn, Sie erweitern Bubblesort noch bspw. um eine Regel, dass der Algorithmus terminiert, wenn es in einer Iteration der äußeren Schleife keine Vertauschungen gab (dann würde der Best Case \(\Theta(n)\) bei schon korrekt sortierten Sequenzen eintreten).

Lassen Sie mich Ihr Beispiel variieren: Ein Sortieralgorithmus habe Komplexität \(\Theta(n^2)\) im Worst Case und \(\Theta(n\log n)\) im Best Case (zum Beispiel Quicksort mit der primitiven Pivotauswahlstrategie "immer das erste Element der Liste als Pivotwert nehmen"). Der Vergleich zweier Elemente (also das, was Comparator.compare in Java leistet) habe Komplexität \(\Theta(m)\) im Worst Case und \(\Theta(1)\) im Best Case (zum Beispiel lexikographischer Vergleich von Strings, deren Länge durch \(m\) beschränkt ist). Dann ist die Komplexität des Gesamtalgorithmus \(\Theta(n^2m)\) im Worst Case und \(\Theta(n\log n)\) im Best Case.

Diese Multiplikation der einzelnen Komplexitäten ist aber nur zulässig, wenn der Worst/Best Case der beiden Bestandteile so wie hier unabhängig voneinander auftreten können, das heißt, Worst Case kann mit Worst Case und Best Case mit Best Case auftreten. Mir fällt spontan kein Beispiel ein, aber zumindest ist nicht a priori ausgeschlossen, dass bei einem zusammengesetzten Algorithmus der Worst Case für den einen Teil nur im Best Case des anderen Teils auftritt und umgekehrt. Dann darf natürlich nicht wie oben einfach multipliziert werden.

Klarer geworden?

KW

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: Übung 4 (Verkettung von Sortierern und Comparator)

Beitrag von joshimoo » 26. Jun 2016 17:37

EDIT: hab zu lange gebraucht zum schreiben :)
Es ist wichtig, das man zu jedem Zeitpunkt weiß wofür seine Variablen stehen.
Daher merke n ist nichts besonderes es bezieht sich lediglich auf eine meist implizit festgelegte Quantität.

Während man ein Thema lernt, empfinde ich es persönlich meist vorteilhaft genau und detailliert zu arbeiten,
sobald man ein Thema dann verstanden hat, nimmt man meist Abkürzungen und nimmt bestimmte Dinge einfach implizit an.

Deshalb mache ich die Erklärung mal etwas ausführlicher, damit die anderen die sich das auch gefragt aber nicht getraut haben zu fragen,
hiervon lernen können :)


Legende:
n = anzahl_listen_elemente
e = element


in unserem Beispiel haben wir einen Comparator auf unserer 2D Matrix definiert.
und in dem von dir gegeben Fall Theta(n^2) bezieht sich das n auf die Dimension der Matrix, außerdem gilt dies nur im Fall das wir quadratische Matrizen betrachten. Im Generellen Fall wäre FCmp(e) = (anzahl_zeilen * anzahl_spalten) * FOp(e) wobei unsere FOp kosten in den Beispielen meist Konstant waren allerdings nicht sein müssen, außerdem siehst du hier bereits das du diese Zerlegung/Abstraktionskette immer weiter führen kannst.

In dem Fall wo die FOp kosten Konstant sind, erwähnt man diese Gar nicht und lässt sie weg, weil x * 1 = x, hier sind wir bei den von mir genannten Abkürzungen die man nimmt wenn man das Material verstanden hat.



jetzt machen wir uns klar, was wir überhaupt betrachten/angeben wenn wir uns mit der Komplexität von Algorithmen beschäftigen.
Siehe dir dazu auch nochmal: Tutorium04 an

Wenn wir sagen das FSort(n) in O(n^2) liegt, dann setzen sich die Kosten so zusammen:
FSort(n) = anzahl_compares * FCmp(e) + anzahl_swaps * FSwp(e)

Da eins dieser Kriterien meist stärker wächst als die anderen, können wir das andere vernachlässigen.
Wir erinnern uns an Selection Sort dort habe ich mal die Gaussiche Summen Formel angeschrieben um zu zeigen das wir damit die Anzahl der benötigten compares im worst case kriegen und das diese von oben durch n^2 beschränkt ist, da wir außerdem wissen das unsere Anzahl der swaps bei Theta(n) liegt können wir diesen Term in unserem Polynom bei der Asymptotischen Betrachtung vernachlässigen und die komplette Komplexität von oben durch O(n^2) beschränken dies gilt nur da in diesem Fall bei beiden die kosten für FCmp und FSwp in Thetat(1) liegen



Man sieht also schnell, das wenn man Dinge verstanden hat dann gibt man diese meist auch nicht mehr so detailliert an und nimmt diese als implizit an. Daher schreibt man auch oft wenn man jetzt FSort(n) betrachte einfach FSort(n) = n^2 wie dir sicher aufgefallen ist hab ich hier auch alle Konstanten Faktoren einfach weggelassen :)


So um jetzt zu deiner eigentlichen Frage zu kommen:

Legende:
n = anzahl_listen_elemente
e = element
y = max_anzahl_zeilen
x = max_anzahl_spalten

FSort(n) = (n^2) * FComp(e)

Hierbei müssen wir noch beachten, das wir für die obere Schranke
Die Maximalen compare Kosten nehmen müssen.

Daher könne wir max_cmp_cost = fuer alle e: max(e->zeilen * e->spalten) für FComp(e) substituieren
oder abstrakter/einfacher O(y * x)

Also insgesamt:
FGesamt(n) = Theta(n^2) * O(y * x)

Unbedingt vermeiden bei einer quadratischen Matrix zu schreiben:
FGesamt(n) = Theta(n^2) * O(n^2) = O(n^4)

Da du damit implizieren würdest das die Anzahl der Listen Elemente eine Aussage über die Kosten pro Listen Element machen würden.
Da nehme ich immer gern das Visualisierungs-Beispiel: du hast 5 Matrizen in deiner Liste also n = 5 allerdings hat jede deiner Matrize = 1 Billion Zeilen sowie 1 Billionen Spalten. Wenn du also nur n betrachtest denkst du dir ja der Aufwand ist nicht so hoch, allerdings gibt es dann eine Böse Überraschung wenn du das tatsächlich implementierst, weil du nicht bedacht hast das diese Kosten/Quantitäten von einander unabhängig sind

Max_S
Erstie
Erstie
Beiträge: 14
Registriert: 16. Apr 2015 17:09

Re: Übung 4 (Verkettung von Sortierern und Comparator)

Beitrag von Max_S » 26. Jun 2016 23:35

@KW: Ja. Jetzt ist es mir deutlich klarer geworden. :)

@joshimoo: Vielen Dank für die ausführliche Erklärung. In der Sprechstunde ist mir das doch teilweise durch den Lappen gegangen... :oops:

Antworten

Zurück zu „AuD: Theoretische Aufgaben“