使用非主定理解决递归方程问题

Question

所以，在之前的一次考试中，我被要求解决以下递归方程而不使用主定理：

T(n)= 9T(n/3) + n^2

很遗憾，我在考试中无法解决它，所以我使用了主定理来解决它，只是为了知道答案（但当然，我没有得到这个问题的学分），现在我想知道如何在没有主定理的情况下解决它，因为在期末考试中，会有类似的问题。如果有人能提供逐步解决方案（并解释），那就太棒了，谢谢！

- busebd12

---

我投票关闭此问题，因为它与编程无关。 - user6655984

Answer 1

诀窍在于不断扩展，直到看到模式。

T(n) 
= 9 T(n/3) + n^2 
= 9(9T(n/3^2) + n^2/3^2) + n^2 
= 9^2 T(n/3^2) + 2n^2
= 9^2 (9 T(n/3^3) + n^2/3^4) + 2n^2
= 9^3 T(n/3^3) + 3n^2
= ...
= 9^k T(n/3^k) + kn^2

这将一直持续到k是使得3^k = n的数字。

假设 T(1)=1，那么你就可以得到 T(n) = n^2 +kn^2 = n^2 + log_3(n) n^2。

因此，看起来 T(n) = O(n^2 logn)，除非我犯了错误。

- MarkG

---

哦，现在扩展的意义清晰多了，谢谢！不过，我仍然困惑于如何假设T(1)=1。 - busebd12

这是一个合理的假设，因为所讨论的算法在该情况下很可能以常数时间运行，即T(1) = O(1)。 - MarkG

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - busebd12

除非问题中另有规定基本情况，否则我认为这个假设是正确的。 - MarkG