如何在递归调用中添加加法树的高度？

Question

我试图找到定义的递归树的高度

$T(n)=T(\frac{n}{5}+36)+n$

我已经发现在内部级别$i$，递归调用相当于：

$$\frac{n}{5^i}+\sum_{k=0}^{i-1}{\frac{36}{5^k}}=\frac{n}{5^i}+36\sum_{k=0}^{i-1}{\left(\frac{1}{5}\right)^k}=\frac{n}{5^i} +36\left(\frac{1-\left(\frac{1}{5}\right)^i}{1-\frac{1}{5}}\right)=\frac{n-45}{5^i}+45$$

注意：最后一步是将很多方程式操作压缩成一个，但我已经仔细检查了它在Wolfram Alpha上的一致性。

但是当我尝试在递归调用$=1$时找到树的高度$ i $：

$$\frac{n-45}{5^i}+45=1$$
After some manipulations:
$$5^i=\frac{45-n}{44}$$
$$i=\log_5{\frac{45-n}{44}}$$

但这意味着$n$必须是$\leq45$，这没有任何意义！

我在哪里错了？

Answer 1

你的表达是正确的：

但是你已经假设了n <= 1的停止条件。

这可以实现吗？不适用于n > 45 - 随着i增加，分数项将消失，因此输入渐近n = 45。你得出的条件告诉你这个 - n只能达到1，如果n < 45，即分数项是负的。

当然，你可以通过采取n <= C C > 45停止条件来解决这个问题。那么深度是：