Master-Theorem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:37 Mo 11.07.2005 | | Autor: | michael7 |
Hallo,
Ist das Master-Theorem fuer die folgenden Rekurrenzen anwendbar?
[mm]T\left(n\right) = 53T\left(\bruch{n}{4}\right) + 2n^3[/mm]
[mm]T\left(n\right) = 36T\left(\bruch{n}{6}\right) + n\log n + n[/mm]
Kann ich bei der ersten Aufgabe folgendes machen, um zu zeigen, dass [m]af\left(\bruch{n}{b}\right) \le cf\left(n\right)[/m] fuer ein c < 1 gilt?
[mm]
53f\left(\bruch{n}{4}\right) \le cf\left(n\right) \gdw 53*2*\left(\bruch{n}{4}\right)^3 \le cf\left(n\right) = c*2*n^3 \gdw 53*\left(\bruch{n}{4}\right)^3 \le cn^3 \gdw \bruch{53}{64}n^3 \le cn^3
[/mm] und das gilt [mm]\forall \bruch{53}{64} \le c < 1[/mm].
Beim zweiten weiss ich nicht wie ich [mm]n*\log n + n[/mm] behandeln soll.
Irgendwelche Tipps?
Danke, Michael
|
|
| |
|
Hallo Michael,
> Ist das Master-Theorem fuer die folgenden Rekurrenzen
> anwendbar?
![[ok]](/images/smileys/ok.gif "[ok]")
>
> [mm]T\left(n\right) = 53T\left(\bruch{n}{4}\right) + 2n^3[/mm]
>
Ich habe mir deine Rechnung für die erste Aufgabe angeschaut, und muß sagen, daß ich genauso vorgegangen wäre. Du hast dich also für den 3ten Fall des Theorems entschieden:
Wenn [mm] $f\left(n\right) [/mm] = [mm] \Omega\left(n^{\log _b a + \epsilon}\right)$ [/mm] für eine Konstante [mm] $\epsilon [/mm] > 0$ erfüllt ist und wenn die Bedingung, die Du angegeben hast, gilt, dann ist [mm] $T\left(n\right) [/mm] = [mm] \Theta\left(f\left(n\right)\right)$.
[/mm]
> [mm]T\left(n\right) = 36T\left(\bruch{n}{6}\right) + n\log n + n[/mm]
>
> Beim zweiten weiss ich nicht wie ich [mm]n*\log n + n[/mm] behandeln
> soll.
Ich habe hier an den ersten Fall des Master-Theorems gedacht:
Wenn [m]\exists \epsilon > 0: f\left( n \right) = \mathcal{O}\left( {n^{\log _b a - \varepsilon } } \right) \Rightarrow T\left(n\right) = \Theta\left(n^{\log _b a}\right)[/m].
Ich denke, wir können mit dieser Nebenrechnung beginnen:
[m]n\log n + n \leqslant n\log n + n\log n \Rightarrow n \leqslant n\log n \Rightarrow 1 \leqslant \log n \Rightarrow 2 \leqslant n[/m]
Und jetzt rufen wir uns nochmal die Definition der [mm] $\mathcal{O}\texttt{-Notation}$ [/mm] in Erinnerung:
[m]a\left( n \right) = \mathcal{O}\left( {b\left( n \right)} \right): \Leftrightarrow \exists c \in \mathbb{R}_{ > 0} \exists n_0 \in \mathbb{N}\,\forall n \geqslant n_0 :\left| {a\left( n \right)} \right| \leqslant c\left| {b\left( n \right)} \right|[/m]
Unser [mm] $n_0$ [/mm] haben wir oben bereits gefunden: [mm] $n_0 [/mm] = 2$. Was ist [mm] $c\!$? [/mm] Wir setzen einfach $c = [mm] 2\!$ [/mm] und erhalten:
[m]n\log n + n = \mathcal{O}\left( {n\log n} \right): \Leftrightarrow \forall n \geqslant \underbrace 2_{n_0 }:\left| {n\log n + n} \right| \leqslant \underbrace 2_c\left| {n\log n} \right|[/m]
Was ist hier [mm] $\log [/mm] _b a$? Nun, [mm] $\log [/mm] _6 36 = 2$. Jetzt müssen wir nur noch das [mm] $\epsilon$ [/mm] bestimmen. Wir wissen, daß der Logarithmus langsamer als jedes Polynom wächst. Er wächst also auch langsamer als die Wurzelfunktion. Es gilt:
[m]\mathcal{O}\left( {n\log n} \right) \subset \mathcal{O}\left( {n\sqrt n } \right) = \mathcal{O}\left( {n^{1.5} } \right)[/m]
Wenn wir also beispielsweise [mm] $\epsilon [/mm] = 0.5$ setzen, müßten wir gerade das gewünschte obige Resultat (also den ersten Fall des M.T.) erhalten.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:11 Fr 15.07.2005 | | Autor: | michael7 |
Danke fuer Deine Hilfe! Es scheint wohl wirklich zu gehen.
|
|
|
|
