Master Theorem < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:03 Di 11.08.2009 | | Autor: | hilado |
| Aufgabe | Folgene Rekurrenzgleichungen sind mit Hilfe des Master Theorems zu lösen:
a) T(n) = 2 * [mm] T(\bruch{n}{2}) [/mm] + n
b) T(n) = 5 * [mm] T(\bruch{n}{2}) [/mm] + [mm] \Theta(n^{3}) [/mm] |
Folgende Lösung zu a):
[mm] log_{b}(a) [/mm] = [mm] log_{2}(2) [/mm] = 1
f(n) = n
zu prüfen: f(n) = [mm] O(n^{1})
[/mm]
n [mm] \in [/mm] O(n) : diese Aussage ist wahr
=> T(n) [mm] \in \Theta(n [/mm] * log(n))
Ist diese Lösung richtig?
zu b habe ich eine Frage: Wie gehe ich mit dem Theta als f(n) um ? Wäre toll, wenn man mir da helfen könnte ...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Mi 19.08.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
