Sortier algorithmen

[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

[Ice-Tea]

MaSTaH schrieb:

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

Gib mal ein Beispiel für eine Funktion, die sich in Form des Master Theorems umformen lässt.