Master-Theorem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:51 So 26.10.2014 | | Autor: | Muskat |
T(n) = [mm] 8T(\textstyle \frac{n}{2}) [/mm] + [mm] 1000n^2 [/mm] ist T(n) [mm] \in \Theta\left( n^{\log_b a} \right).
[/mm]
Aber wie man auf die Laufzeitfunktion T(n) [mm] \in \Theta( n^{3})? [/mm] Ich komme immer auf T(n) [mm] \in \Theta( n^{2})
[/mm]
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:07 So 26.10.2014 | | Autor: | evinda |
a=8 [mm] \geq [/mm] 1, b=2>1, [mm] f(n)=1000n^2
[/mm]
[mm] n^{\log_b a}=n^{\log_2 8}=n^{\log_2 { 2^3 }}=n^{3 \cdot \log_2 2}=n^3
[/mm]
Wir sehen, dass [mm] f(n)=O(n^{\log_b a- \epsilon}), [/mm] für [mm] \epsilon=1
[/mm]
Vom Master Theorem, haben wir, dass [mm] T(n)=\Theta(n^{\log_b a})=\Theta(n^3)
[/mm]
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:48 So 26.10.2014 | | Autor: | Muskat |
Danke für die Antwort! Ich habe hier noch 3 Theoreme. Falls bitte jemand mal die Lösungen prüfen könnte ...
T(n) = [mm] 27T(\textstyle \frac{n}{3}) [/mm] + [mm] n^3 [/mm] (n+1)
Lösung: T(n) [mm] \in \Theta(n^3 [/mm] log n)
T(n) = [mm] 32T(\textstyle \frac{n}{2}) [/mm] + [mm] 16n^4 [/mm] (n log 8)
Lösung: T(n) [mm] \in \Theta(n^5)
[/mm]
T(n) = T(n-1)*n
T(n) [mm] \in \Theta(n!)
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Di 28.10.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
