algorithm - 繰り返し T(n) = T(n^(1/2)) + 1

Question

私はこの再発を見ていて、正しいアプローチを取っているかどうかを確認したかった.

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

したがって、答えは n^(1/2) のシータ境界になります。

Answer 1

ヒント： n = ^22mまたはm=log ² log ₂ nと仮定すると、 ₂ ^{2 m-1} * 2 ^{2 m-1} = 2 ^{2 m}であることがわかっているので、S（m）= T（n）を定義するとSは次のようになります。

S（m）= S（m-1）+ 1→S（m）=Θ（m）→S（m）= T（n）=Θ（log2 _log 2 _n）

一般的な場合に拡張します。

T（n）= T（n / 2）+ 1のような再帰では、各反復で、木の高さを半分に減らします。これはΘ（logn）につながります。ただし、この場合、入力数を2の累乗（2ではなく）で割ると、Θ（log log n）になります。