Hallo kann jemand bitte helfen Sie mir mit der FrageAlgorithmus kosten Master-Theorem mit
T(n)=T(n^(1/2)) + theta (lg lg n)
Das ist, was ich bisher Let Satz
m = lg n
s(m)=s(m/2) + theta (lg m)
Anwendung Master hier
a=1 b=2
m^log 2 (1) = m^0 =1
jetzt stecken.
Sie haben:
a = 1, b = 2
f(m) = Ө(lg(m))
Der zweite Fall des Hauptsatz gilt, wenn:
f(m) = Ө(m^c * lg^k(m))
wo:
c = log_b(a)
Testing this out, haben wir:
f(m) = Ө(lg(m)) = Ө(m^0 * lg(m))
-> c = 0
-> c = log_b(a) = log_2(1) = 0
Also der zweite Fall gilt gelten. Die Lösung für das Wiederauftreten ist daher:
T(m) = Ө(m^c * lg²(m)) = Ө(lg²(m))
Substituieren m, kommen wir zurück auf
T(n) = Ө(lg²(lg(n)))
Ist aber eine Voraussetzung, dass 'b> 1' für den Hauptsatz? –
Ich denke, das sollte' T (m) = Ө sein (m^c * lg² (m)) = Ө (lg² (m)) ', so dass' T (n) = Ө (lg² (lg (n))) '. – Teepeemm
@Teepeemm Ja, du hast Recht. Guter Fang –
Zuerst T (n) = T (n^(1/2)) + theta (lg lg n) kann geschrieben werden als
T (2^(2^k)) = T (2^(2^(k-1))) + Theta (k).
Die Aggregation der obigen Gleichung für k = 1 nach d ergibt T (2^(2^d)) = Theta (d^2). Sei n = 2^(2^d), erhalten wir T (n) = Theta ((lg lg n)^2).
@ TAN soll es k + 1 in der zweiten Zeile sein ?? – aneena
@aneena es ist Quadratwurzel: (2^(2^k))^(1/2) = 2^(2^k/2) = 2^(2^(k-1)). –
'n^(1/2) = sqrt (n)' und '(lg n)/2! = Sqrt (n)', so scheint Ihre Arbeit bisher falsch zu sein. Müssen Sie unbedingt die Master-Methode verwenden? – IVlad
@IVlad 'lg (sqrt (n)) == lg (n)/2 == m/2' (per Definition). Ist das nicht richtig? –
@Asad - ja, das ist richtig. Aber das OP hat 'T (sqrt (n))', und ich sehe nicht, wie er von diesem zu 'T (lg (sqrt (n)) = T (m/2) 'gekommen ist. Es wäre richtig, wenn er hatte 'T (lg sqrt (n))'. – IVlad