algorithm - 计算递归关系的封闭形式 : Fractions

Question

给定:T(1) = 1

您将如何计算 T(n) = T(n/4) + 1 的封闭形式？

我的回答是:

T(n) = T(n/4) + 1
T(n) = T(n/8) + 1 + 1
T(n) = T(n/16) + 1 + 1 + 1

等等。这是处理这个方程式的正确方法吗？我是否遗漏了一些重要的关键步骤？

Answer 1

我们有 T(n)=T(n/4)+1

现在求 T(n/4) 即 T(n/4)=T(n/(4^2))+1
因此第二项是 T(n)=T(n/(4^2))+2
同样，第 k 项将是 T(n)=T(n/(4^k))+k
现在将 n=4^k 代入上式的 RHS，因此我们得到 T(n)=T(1)+k
=> T(n)=1+k
但是 n = 4^k
=> k = log n 其中 log 的底数是 4。
因此 T(n)= (1+log n );其中日志的基数是 4。