Sortier algorithmen

Ice-Tea

Ich beschäftige mich aktuell mit Sortier algorithmen.

Zum Starten verwende ich folgende Website:
http://www.sortieralgorithmen.de/

Die Website hat eine Rubrik Mathematik:
http://www.sortieralgorithmen.de/mathematics.htm

Wäre nett, falls jemand diese Formeln erläutern könnte (erklären).
Speziell diese Formeln: die ersten 3 und die letzten 6

Danke und Gruss

Yankee

Es geht um die Einordnung der Laufzeiten von Algorithmen in sogenannte Komplexitätsklassen.
Beispiel: Quicksort liegt in der Menge O(n*log_2(n))
D.h. Quicksort braucht, um ein n-elementiges Array zu sortieren, c*n*log_2(n) Befehle.

Einfaches Beispiel:

int a = 0;
for(int i = 0; i < n; i++)
{
 a = a+1;
}

Du zählst zunächst die Anzahl der Befehle ausserhalb der Schleife. Das ist genau 1 (a = 0), dazu kommen 2 Befehle, die vor dem ersten Durchlauf der Schleife ausgeführt werden (i = 0; i < n), die zählen, da es beide atomare Operationen sind, jeweils 1.
D.h. ausserhalb der Schleife hast du 3 Befehle.
So, jetzt wird diese Schleife genau n mal ausgeführt. Bei jedem Schleifendurchlauf wird zunächst i < n geprüft (1 Befehl) und i erhöht (i++, auch ein Befehl). Innerhalb des Schleifenkörpers ist eine Operation, die aus 2 atomare Operationen besteht (a + 1 und die Zuweisung a =).
D.h., für ein bestimmtes n werden
1 + 2 + n*(2 + 2) = 4*n + 3
Befehle ausgeführt.
Also liegt dieser "Algorithmus" in der Menge O(n), denn
Ab einem bestimmten n (nämlich n = 1) ist 4*n + 3 <= 5*n
Schau Dir die dritte Formel auf der von Dir erwähnten Seite an.
In diesem Fall wäre c = 5 und x_0 = 1 (unser n).

f(x) Element (oder O(n) bedeutet genau das da oben.
O(n) ist die Menge der Funktionen, die nach oben von der Funktion g(x) = c*x beschränkt sind.
Die anderen Formeln dort kannst Du Dir jetzt selber überlegen. Bei den Matser-Theoremen weiter unten habe ich gerade keinen Plan.

Ich hoffe, das war etwas zu verstehen, ansonsten sei verwiesen auf folgendes Skript:
http://www.dvs1.informatik.tu-darmstadt.de/lectures/ws04-05/inf3/folien.html
(die erste PDF-Datei dort)

Jester

Yankee schrieb:

Beispiel: Quicksort liegt in der Menge O(n*log_2(n))

Nein. Quicksort ist O(n^2). O-Notation betrachtet den worst-case. Und der findest statt, wenn Du immer so ungeschickt das Pivotelement wählst, daß Du immer das kleinste noch nicht sortierte erwischst... dann ist der Aufwand n+(n-1)+...+1 = O(n^2). Im Mittel über alle Verteilungen ist die Laufzeit von Quicksort (also die erwartete Laufzeit, nicht worst-case) aber O(n*log n).

Yankee schrieb:

Ab einem bestimmten n (nämlich n = 1) ist 4*n + 3 <= 5*n

huh? dachte immer 7 > 5
richtig wäre: n=3

MfG Jester

Yankee

Jester schrieb:

Yankee schrieb:

Beispiel: Quicksort liegt in der Menge O(n*log_2(n))

Nein. Quicksort ist O(n^2). O-Notation betrachtet den worst-case. Und der findest statt, wenn Du immer so ungeschickt das Pivotelement wählst, daß Du immer das kleinste noch nicht sortierte erwischst... dann ist der Aufwand n+(n-1)+...+1 = O(n^2). Im Mittel über alle Verteilungen ist die Laufzeit von Quicksort (also die erwartete Laufzeit, nicht worst-case) aber O(n*log n).

stimmt

Yankee schrieb:

Ab einem bestimmten n (nämlich n = 1) ist 4*n + 3 <= 5*n

huh? dachte immer 7 > 5
richtig wäre: n=3

MfG Jester

äh ja .. voll verödelt ..

Bashar

Jester schrieb:

Nein. Quicksort ist O(n^2). O-Notation betrachtet den worst-case.

Minor Nitpick: O-Notation betrachtet eigentlich erstmal gar keine cases, und Quicksort "ist" auch nicht O(irgendwas). f(x) = O(g(x)) heisst nur, dass f nicht schneller wächst als g. Man kann also ohne weiteres sagen, die Laufzeit von Quicksort im Average-Case ist in O(n log n).

Ice-Tea

Bashar schrieb:

Jester schrieb:

Nein. Quicksort ist O(n^2). O-Notation betrachtet den worst-case.

Minor Nitpick: O-Notation betrachtet eigentlich erstmal gar keine cases, und Quicksort "ist" auch nicht O(irgendwas). f(x) = O(g(x)) heisst nur, dass f nicht schneller wächst als g. Man kann also ohne weiteres sagen, die Laufzeit von Quicksort im Average-Case ist in O(n log n).

Erstmals danke @Yankee für den ausführlichen Beitrag.
Unklarheiten:
Die Konstante c, wie lässt sich diese berechnen?
Und für was steht g?

Jester

@Bashar: hast recht. Mit der Zeit wird man da halt ein bißchen schludrig. Zu sagen, daß (der normale) Quicksort einen Aufwand von O(n*nog(n)) Schritten habe ist dennoch inkorrekt. Das wollte ich eigentlich nur zeigen. Aber ich sollte vielleicht trotzdem etwas mehr auf meine Notation achten.

Yankee

Wenn wir schon beim Klugscheissern sind:
f(x) = O(g(x)) ist mathematisch falsch, denn O(g(x)) bezeichnet eine Menge. Es heisst also
f(x) Element O(g(x))

@Ice-Tea:
g(x) ist etwa so etwas:
n^2
n*log(n)
n!

c*g(x) ist die obere Schranke für eine Menge von Funktionen, wie oben beschrieben.

Jester

Jo, dann schieb ich vielleicht doch mal schnell die exakte Definition von O(g(x)) an.

eine Funktion f(x) ist in O(g(x)) :<=> es ex. c aus N und n0 aus N: für alle n>=n0: f(x) <= c*g(x)

Man fordert also, daß ein vielfaches von g(x) eine obere Schranke von f(x) ist.

Für f(x) in O(g(x)) schreibt man auch oft f(x) = O(g(x)). Hat sich halt so eingebürgert.

MfG Jester

Ice-Tea

Yankee schrieb:

Wenn wir schon beim Klugscheissern sind:
f(x) = O(g(x)) ist mathematisch falsch, denn O(g(x)) bezeichnet eine Menge. Es heisst also
f(x) Element O(g(x))

@Ice-Tea:
g(x) ist etwa so etwas:
n^2
n*log(n)
n!

c*g(x) ist die obere Schranke für eine Menge von Funktionen, wie oben beschrieben.

Ersteres ist nun klar.

Zu c :
Wie berechne ich c? Kann ich c beliebig wählen oder muss ich es berechnen?
In deinem Post hast du ja geschrieben "bei uns ist c=5" (woher hast du das genommen?)

Jester

wenn DU zeigen willst, daß eine Funktion f(x) in O(g(x)) ist, dann mußt Du ein solches c finden. Wie man das findet kann von Fall zu Fall recht unterschiedlich sein. Es kann ein beliebiger Wert sein, aber er muß konstant sein.

Zum Beispiel kann man zaigen, daß 3*n^2+5*n+17 in O(n^2) ist.

geht folgendermaßen: 3*n^2+5*n+17 <= 3*n^2+5*n2+17*n^2 = 25*n^2, wähle also c=25. Das ist zwar für die meisten Fälle viel zu groß, ist aber egal. Hauptsache es gibt eines.

MfG Jester

Walli

Yankee schrieb:

Wenn wir schon beim Klugscheissern sind:
f(x) = O(g(x)) ist mathematisch falsch, denn O(g(x)) bezeichnet eine Menge. Es heisst also
f(x) Element O(g(x))

Es ist in der Informatik durchaus üblich f(x) = O(g(x)) zu schreiben. Klugscheißerei ist hier also unangebracht.

Yankee

Da wir im Mathe-Forum sind, habe ich ja auch geschrieben, dass es mathematisch falsch ist. Ausserdem sollte der Beitrag auch nicht so ganz ernst sein

Ice-Tea

Auf der von mir erwähnten Seite geht's noch um:

- Formeltransformation
- Master Theorem

Hat noch jemand Lust diese beiden Formeln zu erklären?

Walli

Öh, Lust nicht gerade. Leih dir Introduction to Algorithms von Cormen aus und schau es dir dort an. Das Mastertheorem wird darin sehr gut erklärt (mit Beweis!). Im Prinzip ist es nur ein Kochrezept zum abschätzen von Rekurrenzgleichungen der Form: $T(n) = a\cdot T\left(\left\lceil\frac{n}{b}\right\rceil\right) + f(n)$ bzw. $T(n) = a\cdot T\left(\left\lfloor\frac{n}{b}\right\rfloor\right) + f(n)$ , wobei a und b Konstanten ≥ 1 sind. Ich müsste es in meinen Unterlagen suchen und es dauert ziemlich lange das komplette Mastertheorem abzutechen... Vielleicht findest du ja bei google oder in dem von mir erwähnten Buch Hilfe.

EDIT: Einer der ersten Treffer bei google: http://www.soft.uni-linz.ac.at/Teaching/Begleitmaterial/Uebungen/_Algorithmen_und_Datenstrukturen_2/02 Rekurrenzen.pdf

Ice-Tea

MaSTaH schrieb:

Öh, Lust nicht gerade. Leih dir Introduction to Algorithms von Cormen aus und schau es dir dort an. Das Mastertheorem wird darin sehr gut erklärt (mit Beweis!). Im Prinzip ist es nur ein Kochrezept zum abschätzen von Rekurrenzgleichungen der Form: $T(n) = a\cdot T\left(\left\lceil\frac{n}{b}\right\rceil\right) + f(n)$ bzw. $T(n) = a\cdot T\left(\left\lfloor\frac{n}{b}\right\rfloor\right) + f(n)$ , wobei a und b Konstanten ≥ 1 sind. Ich müsste es in meinen Unterlagen suchen und es dauert ziemlich lange das komplette Mastertheorem abzutechen... Vielleicht findest du ja bei google oder in dem von mir erwähnten Buch Hilfe.

EDIT: Einer der ersten Treffer bei google: http://www.soft.uni-linz.ac.at/Teaching/Begleitmaterial/Uebungen/_Algorithmen_und_Datenstrukturen_2/02 Rekurrenzen.pdf

Ich werde das Theorem in erwähntem Buch nachschauen.

Nehmen wir wieder die Funktion von vorhin: f(x)=4*n+3
Ich möchte mit dem Master Theroem beweisen, dass diese Funktion in n^2 liegt.
Wie mache ich das?
Welche Werte muss ich für a und b einsetzen (Wie verwende ich die Formel)?

Walli

Geht nicht, weil sie nicht der Form des Mastertheorems entspricht.

Ganz einfache Übung:
$T(n) = 9\,T\left(\frac{n}{3}\right) + n$

Darauf kannst du sofort das Master-Theorem anwenden. Probier es einfach mal, ist nichts schweres dabei. Rechne einfach $\log_b{a}$ aus und schaue, welcher der 3 Fälle des Master-Theorems eintritt .

Ice-Tea

MaSTaH schrieb:

Geht nicht, weil sie nicht der Form des Mastertheorems entspricht.

Ganz einfache Übung:
$T(n) = 9\,T\left(\frac{n}{3}\right) + n$

Darauf kannst du sofort das Master-Theorem anwenden. Probier es einfach mal, ist nichts schweres dabei. Rechne einfach $\log_b{a}$ aus und schaue, welcher der 3 Fälle des Master-Theorems eintritt .

Einverstanden.
Aber irgendwie muss sich eine Funktion in die Form des Master-Theorems umformen lassen.

Walli

Nope, nicht immer. Aber es gibt andere Methoden um Rekursionsgleichungen anderer Form abzuschätzen (Induktion etc.).

Ice-Tea

Eine Funktion zwischen geschlossener und offener Form umformen.
Ich suche Beispiele dafür! Je mehr desto besser