Mastermethode < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen Sie folgende Aussage mit Hilfe der Master-Methode:
Sei $T(1)=1, T(n) = 3T(n/4) + n [mm] \cdot [/mm] log(n)$ für alle $n [mm] \geq [/mm] 1$, dann: $T(n) = [mm] \Theta(n \cdot [/mm] log(n))$ |
Ich soll das ja mit der Master-Methode machen: Da gibt's ja 3 Fälle:
1. Fall:
$f(n) = [mm] O(n^{log_b(a) - \epsilon}) \Leftrightarrow [/mm] n [mm] \cdot [/mm] log(n) = [mm] O(n^{log_4(3) - \epsilon} \Leftrightarrow [/mm] n [mm] \cdot [/mm] log(n) = [mm] O(n^{0,7924... - \epsilon})$ [/mm] Da ist doch nun ein Widerspruch, oder?
2. Fall:
$f(n) = [mm] O(n^{log_b(a)}) \Leftrightarrow [/mm] n [mm] \cdot [/mm] log(n) = [mm] \Theta(n^{log_4(3)}) [/mm] Da ist doch nun wieder ein Widerspruch, oder?
3. Fall:
$f(n) = [mm] \Omega(n^{log(a)+\epsilon}) \wedge [/mm] a [mm] \cdot f(\frac{n}{b}) \leq [/mm] c [mm] \cdot [/mm] f(n) [mm] \wedge \forall [/mm] n [mm] \geq n_0 \Leftrightarrow \underbrace{n \cdot log(n) = \Omega(n^{log_4(3)+\epsilon})}_{\text{hier gibts ja schon wieder einen Widerspruch?}} [/mm] = ... [mm] \wedge [/mm] ... [mm] \wedge [/mm] = ...$
Gilt das nun einfach nicht, oder hab ich Fehler gemacht?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 So 08.04.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
