algorithm - マスター定理を使用したアルゴリズム コスト

Question

こんにちは、誰でも質問を手伝ってくれますか

T(n)=T(n^(1/2)) + theta (lg lg n)

これが私がこれまでやってきたことです

m = lg n
s(m)=s(m/2) + theta (lg m)

ここでマスター定理を適用

a=1 b=2
m^log 2 (1) = m^0 =1 

今立ち往生。

Answer 1

あなたが持っている：

a = 1, b = 2
f(m) = Ө(lg(m))

マスター定理の 2 番目のケースは、次の場合に適用されます。

f(m) = Ө(m^c * lg^k(m))

どこ：

c = log_b(a)

これをテストすると、次のようになります。

f(m) = Ө(lg(m)) = Ө(m^0 * lg(m)) 
-> c = 0
-> c = log_b(a) = log_2(1) = 0

したがって、2 番目のケースが適用されます。したがって、再発の解決策は次のとおりです。

T(m) = Ө(m^c * lg²(m)) = Ө(lg²(m))

に置き換えるmと、 に戻ります

T(n) = Ө(lg²(lg(n)))

Answer 2

まず、T(n) = T(n^(1/2)) + theta(lg lg n) は次のように記述できます。

T(2^(2^k)) = T(2^(2^(k-1))) + シータ(k)。

上記の方程式を k=1 から d まで集計すると、T(2^(2^d)) = theta(d^2) が得られます。n=2^(2^d) とすると、T(n) = theta( (lg lg n)^2 ) が得られます。