algorithm - 再帰関係をマスター定理で解く?

Question

誰かがこの解決策をもう少し明確にしてもらえますか?

T(n) = 2T(n^1/2) + ログ n

解決：

k = log n とします。

T(n) = T(2^k)=2T(2^(k/2)) + k

これに式 S(k) = T(2^k) を代入します。

私たちはそれを得る

S(k)=2S(k/2) + k

さて、この再帰方程式により、マスター定理を使用することができます。

S(k) は O(k log k) です。T(n) の代入は、T(n) が O(log n log log n) であることを意味します。

Answer 1

n を 2 で何回割り切れますか? Log_2(n) 回。Log_2(n) は、n を得るために 2 を何乗する必要があるかということです。

また、loglog(n) は n の平方根をとれる回数なので、これを知っていれば、その置換はそれほど必要ではないかもしれません。