Master Theorem |
16.12.2015, 17:42 | Xyarvius | Auf diesen Beitrag antworten » |
Master Theorem Finden Sie das Theta-Verhalten für die folgenden Rekursionen, wobei n > 1 und T(1) = d > 0. (1) T(n) = 3*T(n/2)+ sqrt((n^4)+3) (2) T(n) = 2*T(n/3) + c*log3(n), mit konstantem c > 0. Betrachten Sie lediglich den Fall n = 3^k. Meine Ideen: (1) Ich bin mir nicht sicher, ob man das so machen kann: a=3, b=2, f(n)=sqrt((n^4)+3) n^logb(a) = n^log2(3) < n^2 = sqrt(n^4) -> n^log2(3) < sqrt((n^4)+3) ->T(n) Element von Theta(sqrt((n^4)+3)) (Master Theorem - 3. Fall) (2) Hier bin ich jetzt gänzlich überfragt ... kann man hier den Master Theorem überhaupt anwenden? Wie gehe ich vor? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|