Master-Theorem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi alle zusammen,
ist folgendes richtig?
T(n) = 53T(n/4) + [mm] 2n^3
[/mm]
Master-Theorem-Fall 3:
Da [mm] log_{4} [/mm] 53 liegt zwischen 2 und 3 und somit gilt:
f(n) = [mm] \Omega (n^{log_{4} 53 + \varepsilon})
[/mm]
Zudem gilt:
53 f(n/4) < cf(n)
53 2 [mm] \frac{n^3}{64} [/mm] < 2c [mm] n^3 [/mm]
[mm] \frac{53}{64} [/mm] < c
Somit gilt auch c < 1, wie es bei Regel 3 beim Masther-Theorem verlangt ist.
Somit liegt T(n) [mm] \in \Theta(n^3)
[/mm]
Wäre cool, wenn Ihr mir sagen könntet, ob das so richtig ist.
|
|
| |
|
Hallo Mathematiker!
> Wäre cool, wenn Ihr mir sagen könntet, ob das so richtig
> ist.
Also ich würd' sagen, daß Du richtig gerechnet hast. $c [mm] \ge \bruch{53}{64}$ [/mm] bedeutet ja nur, daß man die Konstante ab diesem Wert wählen kann. Wenn wir uns hierbei auf Konstanten < 1 beschränken, wählen wir $c$ halt aus dem Intervall [mm] $\left[\bruch{53}{64}, 1\right)$. [/mm] Also z.B. c = 0.9.
Somit müßte deine Vorgehensweise schon stimmen.
Grüße
Karl
|
|
|
| |
|
Jo seh ich auch so, was den Rechenweg betrifft. Danke für deine Antwort.
MfG Andi
|
|
|
|
