Frage(n) zum Master-Theorem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi alle zusammen,
also das Master-Theorem ist ja vom Grundprinzip her sehr leicht zu verstehen, jedoch habe ich bei manchen Aufgaben in denen die Funktion f(n) in der Rekursionsgleichung aus mehreren zusammengesetzten Termen bestehen Probleme mit der genauen Einordnung.
Zwei Beispiele hierzu:
T(n) = [mm] 64T(\frac{n}{8}) [/mm] + 1042 [mm] n^2 [/mm] + 1000000n
So [mm] \log_{8}64 [/mm] = 2.
Ich hätte jetzt gesagt, dass Fall 3 gilt, da meiner Meinung nach
1042 [mm] n^2 [/mm] + 1000000n [mm] \in \Omega(n^2) [/mm] liegt. Aber das ist anscheinend nicht so, da in der Musterlösung gesagt wird, dass es [mm] \in \Theta(n^2) [/mm] liegt, was ich nicht wirklich verstehe.
Findet diese 1000000n nur Bedeutung, wenn da jetzt anstatt eines Plus ein Multiplikationszeichen stehen würde?
2. Beispiel:
T(n) = [mm] 27T(\frac{n}{3}) [/mm] + [mm] \frac{n^3}{\log_{9}^{3}(n)}
[/mm]
Warum ist [mm] \frac{n^3}{\log_{9}^{3}(n)} [/mm] nicht in [mm] \Theta(n^3), [/mm] sondern in [mm] O(n^3)?
[/mm]
Wäre schön, wenn mich da mal jemand aufklären könnte *gg*.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:09 So 28.08.2005 | | Autor: | Frank05 |
> also das Master-Theorem ist ja vom Grundprinzip her sehr
> leicht zu verstehen, jedoch habe ich bei manchen Aufgaben
> in denen die Funktion f(n) in der Rekursionsgleichung aus
> mehreren zusammengesetzten Termen bestehen Probleme mit der
> genauen Einordnung.
so wie ich das sehe liegt das Problem eher im Verstaendnis der Landau-Symbole.
Zumindest haben deine Fragen mal nichts mit dem Master-Theorem zu tun.
> Ich hätte jetzt gesagt, dass Fall 3 gilt, da meiner Meinung
> nach
>
> 1042 [mm]n^2[/mm] + 1000000n [mm]\in \Omega(n^2)[/mm] liegt. Aber das ist
> anscheinend nicht so, da in der Musterlösung gesagt wird,
> dass es [mm]\in \Theta(n^2)[/mm] liegt, was ich nicht wirklich
> verstehe.
Also nochmal zurueck zur Definition von [mm]\Omega, \Theta[/mm]:
[mm]f \in \Omega(g) \Leftrightarrow \exists c > 0 \exists n_0 > 0 \forall n >= n_0 : f(n) >= c*g(n)[/mm]
Um also [mm]1042*n^2+1000000*n >= c*n^2[/mm] zu erfuellen genuegt uns schon [mm]c = 1042, n_0 = 1[/mm].
Also liegst du mit deiner Vermutung richtig.. aber wo ist jetzt das Problem? Was war denn nochmal die andere Klasse:
[mm]f \in \Theta(g) \Leftrightarrow f \in O(g) \cap \Omega(g)[/mm]
Wenn also in der Musterloesung steht, dass es in [mm]\Theta(n^2)[/mm] liegt, dann muss es auch noch in [mm]O(n^2)[/mm] liegen, was natuerlich auch der Fall ist (ich denke das sollte klar sein.. sonst nochmal nachfragen).
Demzufolge steht da nichts falsches. Diese Funktion ist einfach in allen 3 dieser Mengen enthalten.
> Findet diese 1000000n nur Bedeutung, wenn da jetzt anstatt
> eines Plus ein Multiplikationszeichen stehen würde?
Im Prinzip ja.. da es hier nur um die asymptotische Groesse geht spielt ein additiver linearer Term keine Rolle gegenueber dem quadratischen Term. Bei Multiplikation erhaelt man natuerlich [mm]n^3[/mm], was dann durchaus etwas aendert.
>
> 2. Beispiel:
>
> T(n) = [mm]27T(\frac{n}{3})[/mm] + [mm]\frac{n^3}{\log_{9}^{3}(n)}[/mm]
>
> Warum ist [mm]\frac{n^3}{\log_{9}^{3}(n)}[/mm] nicht in [mm]\Theta(n^3),[/mm]
> sondern in [mm]O(n^3)?[/mm]
Also etwas genauer draufschauen:
[mm]f \in O(g) \Leftrightarrow \exists c > 0 \exists n_0 > 0 \forall n >= n_0 : f(n) <= c*g(n)[/mm]
Und demnach: [mm]\frac{n^3}{\log_{9}^{3}(n)} <= c*n^3 \Leftrightarrow \frac{1}{\log_{9}^{3}(n)} <= c[/mm]
[mm]\Leftrightarrow \frac{log(9)}{c^\frac{1}{3}} <= log(n) \Leftrightarrow n >= exp(\frac{log(9)}{c^\frac{1}{3}})[/mm]
Und da steht dann auch schon wie wir unseren Wert [mm]n_0[/mm] waehlen muessen, damit die Gleichung [mm]\forall n>=n_0[/mm] erfuellt ist. Demnach ist die Funktion also schonmal in [mm]O(n^3)[/mm]. Um auch in [mm]\Theta(n^3)[/mm] zu sein muessen wir noch pruefen, ob sie in [mm]\Omega(n^3)[/mm] ist. Da dabei aber gerade aus dem [mm]<=[/mm] ein [mm]>=[/mm] wird kann das nicht der Fall sein. (Sonst haben wir am Schluss eine obere Schranke fuer n und [mm]\forall n >= n_0[/mm])
Und somit kann die Funktion auch nicht im Schnitt dieser beiden Klassen und damit nicht in [mm]\Theta(n^3)[/mm] liegen.
|
|
|
|
