用迭代/代入法求解递推式T(n)=T(n/3)+O(1)及对数底数探究

我来用递归树法和代入法帮你把这个递推式拆明白，搞清楚对数的底数到底是什么~

递归树法求解 #

首先，我们把递推里的O(1)换成一个具体的常数c（毕竟O(1)就是指常数级别的时间开销），这样递推式可以写成：
T(n) = T(n/3) + c

接下来我们一步步构建递归树：

• 第0层（根节点）：对应问题规模n，开销是c
• 第1层：只有1个子节点，问题规模缩小到n/3，开销还是c
• 第2层：同样是1个子节点，规模变成n/3²，开销依旧是c
• ...
• 一直递归下去，直到问题规模缩小到1（因为T(0)=0，这里我们可以把T(1)当作基准情况，不影响最终的渐近阶），此时n/3ᵏ = 1，解这个式子得到k = log₃n，也就是递归树总共有k+1层。

把所有层的开销加起来：每层都是c，总共有log₃n + 1层，所以总开销是c*(log₃n + 1)。忽略常数项和系数，最终结果就是Θ(log₃n)。

你提到假设n=2ᴷ，那我们调整一下视角：n=2ᴷ时，log₃n = log₃2ᴷ = K*log₃2，总开销就是c*(K*log₃2 +1)，转换回n的形式还是Θ(log₃n)——毕竟对数换底公式告诉我们，不同底数的对数只差一个常数系数，这也是为什么Master定理里只写Θ(logn)的原因，但具体到精确形式，底数就是3。

代入法验证 #

我们先猜测T(n) = a*log₃n + b（a、b是常数），然后代入递推式验证：

左边：T(n) = a*log₃n + b
右边：T(n/3) + c = a*log₃(n/3) + b + c = a*(log₃n - log₃3) + b + c = a*log₃n -a + b + c

让左右两边相等，消去相同项后得到：0 = -a + c，也就是a = c。

再看基准情况：当n=1时，T(1) = T(1/3) + c，这里1/3向下取整是0，所以T(1) = T(0) + c = 0 + c = c。把n=1代入我们的猜测式，T(1)=a*log₃1 + b = 0 + b = b，所以b = c。

最终得到T(n) = c*log₃n + c = c(log₃n +1)，和递归树法的结果完全一致，验证了我们的结论。

内容的提问来源于stack exchange，提问作者Arjun Singh