通过替换递归求解
Recurrence solving by substitution
T(n) = { 0 If n = 0
{ T(square root n) + 1 If n > 0
我正在尝试使用替换来解决这个问题
我的猜测：O(lg lg n)
通过归纳法
T(n) = c lg lg n
T(n) =< c (lg lg square root n) + 1
因为 square root n = n^1/2 =< c(1/2 lg lg n) + 1
我无法继续这部分以获得 lg lg n 并且我看到了许多使用权力的解决方案。还有别的办法吗？
谁能画个递归树帮我理解下？
1
||
n^1/2
||
n^1/4
||
n^1/8
T(n) = 1 + .......
理解这一点的最简单方法是使用 2 的幂，正如许多其他答案所说的那样，但是，要继续您提到的步骤，假设 T(n) = lg lg n （忽略常数，因为这是一个精确的答案）。
那么我们有：
T(sqrt(n)) = lg lg (sqrt(n)) = lg (1/2 * lg (n))
= lg (2^(-1) * lg(n))
= -1 + lg lg (n)
= -1 + T(n)
如你所见，T(n) = T(sqrt(n)) + 1
T(n) = { 0 If n = 0
{ T(square root n) + 1 If n > 0
我正在尝试使用替换来解决这个问题
我的猜测：O(lg lg n)
通过归纳法
T(n) = c lg lg n
T(n) =< c (lg lg square root n) + 1
因为 square root n = n^1/2 =< c(1/2 lg lg n) + 1
我无法继续这部分以获得 lg lg n 并且我看到了许多使用权力的解决方案。还有别的办法吗？
谁能画个递归树帮我理解下？
1
||
n^1/2
||
n^1/4
||
n^1/8
T(n) = 1 + .......
理解这一点的最简单方法是使用 2 的幂，正如许多其他答案所说的那样，但是，要继续您提到的步骤，假设 T(n) = lg lg n （忽略常数，因为这是一个精确的答案）。
那么我们有：
T(sqrt(n)) = lg lg (sqrt(n)) = lg (1/2 * lg (n))
= lg (2^(-1) * lg(n))
= -1 + lg lg (n)
= -1 + T(n)
如你所见，T(n) = T(sqrt(n)) + 1