我正在尝试解决这种重复关系。这是我到目前为止所尝试的，但我认为我错了。我真的很感激一些指导。
这是我要解决的递归关系：- 2T(n^1/2) + C
T(n) = 2T(n^1/2) + C
2((2T(n^1/4)+C) + C
>> 4T(n^1/16) + 3C
>> 8T(n^1/256) + 6C
所以我可以把它表述成这个代数表达式：-
(2^k)T(n^(1/2^k)) + 2k
所以为了解决递归关系，我简单地说
n^(1/(2^k)) = 1
Therefore:- 2k = log (base n) 1
But this makes k = 0....
我不认为这是正确的。请给我建议，我很高兴得到一些帮助！
我的尝试。（警告：我不确定替换是不是正确的做法。让我们试一试。）
假设T(x) = 1x < 2
使用 T(1) 是不行的（见我的评论），所以也许我们可以尝试计算 T(2)
T(2) = 2 * T(sqrt(2)) + C = 2 + C
现在我们搜索 k 这样n^(1/2^k) = 2 + C
1/(2^k) = log_n(2 + C) [base n log]
1/log_n(2 + C) = 2^k
log_(2 + C) n = 2^k [1 / log_a b = log_b a]
lg n / lg (2 + C) = 2^k [change-of-base]
c2 lg n = 2^k [since lg (2 + C) is fixed we put c2 = 1 / lg (2 + C)]
k = lg (c2 * lg n) = (lg c2) + lg lg n
k = c3 + lg lg n [since lg c2 is fixed]
现在我们将 k 代入T(N) = 2^k + 2k并找到
T(n) = 2^c3 * lg n + 2*c3 + lg lg n
现在如果我们把
T(n) = c1 lg n + c2 lg lg n
其中 c1 和 c2 是固定的，与我们上面使用的不同。