如何求解 T(n) = T(0.2*n^0.5) + 1？

Question

我知道怎么解决T(n) = T(n^0.5) + 1。让m = lg n和S(m) = T(2^m)。然后我们得到 S(m) = S(m/2) + 1。我们知道 S(m) = Θ(lg m)。所以T(n) = Θ(lg lg n)。

但是我不确定如何解决T(n) = T(0.2*n^0.5) + 1。 0.2 让我失望了。如果我使用相同的方法，我不确定如何弄清楚 S(m) 是什么。

Answer 1

在新的，你得到

S(lg n) = S(lg 0.2 + 0.5 lg n) + 1
S(m) = S(lg 0.2 + 0.5 m) + 1.

诀窍是替换R(x) = S(m + 2 lg 0.2)。

R(x) = S(m + 2 lg 0.2)
     = S(lg 0.2 + 0.5 (m + 2 lg 0.2)) + 1
     = S(0.5 m + 2 lg 0.2) + 1
     = R(0.5 x) + 1

然后解开替换并得出结论 T(n) = Theta(lg lg n)，和以前一样。

How to solve T(n) = T(0.2*n^0.5) + 1?