Master Theorem (Laufzeiten) < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Die folgenden Terme beschreiben die rekursiven Laufzeiten T(n).... diverser Divide und Conwuer Algorithmen. Wenden sie das Master Theorem an um die diese Rekurrenzen asymptotisch aufzulösen, wobei e die eulersche Zahl bezeichnet.
a) 4T (n/4) + n
b) T (n/42) + 3te Wurzel von n
c) [mm] 10^9* [/mm] T(n/1000)+ [mm] n^e [/mm] |
Hallo ihr Lieben,
ich stecke gerade in meinen Prüfungsvorbereitung für eine Informatik/Mathe in der es um Laufzeiten von Programmen geht.
Nun bin ich mir nicht ganz sicher wie das Master Theorem anzuwenden ist. Ich weiss, dass es drei Fälle gibt in denen es zu unterscheiden gilt.
1. Fall --> c <1
2. Fall --> c = 1
3. Fall --> c > 1
Was ist jetzt aber c?
Ich habe mal a) gemacht.
T(n) = 4T (n/4) + n. /////// a= 4; b=4; f(n)= n
n^logb(a) = n^(log4(4) = [mm] n^1 [/mm] vs. f(n)=n
Da [mm] n^1 [/mm] und f(n) gleich sind würde ich jetzt sagen dass das Fall 2 ist. --> laufzeit log n.
Aber was genau hat das mit der Zahl 1 (von den fällen) zu tun?
b)
T(n/42)+ 3square(n) //////// a= 1 ; b=42; f(n)=3square(n)
n^(logb(a))= n^ log42(1) = [mm] n^0 [/mm] vs. 3square(n) = [mm] n^1/3
[/mm]
Was genau muss ich mir da jetzt anschauen um den Fall rauszubekommen?
Ich hoffe ihr könnt mir helfen
Liebe Grüsse
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:56 Di 18.03.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
