如何用树方法求解递推式8T(n/2)+n²？结果为何是n³？

嘿，我最近在啃一个递推问题，可越想越觉得自己的思路不对劲儿，想跟大家聊聊我的困境！

我平时处理这类问题的固定流程是这样的：

• 先揪出递归树某一行里的最大值（这次是n²）
• 反复拆分这个最大值，试图找出数值之间的内在联系
• 找到规律后就着手数学推导
• 最后把推导出来的结果和根节点的值相乘

但这次的问题，正确答案明明是n³，我却怎么也想不通这个结果是怎么来的。

给大家描述下递归树的样子：

根节点是n²，同时对应一个n的项；第一层把n²拆成两个(n/2)²，这一层也有一个n的项；往下每一层，每个节点都会拆成两个更小的平方项，同时每一层都保留一个n的项，直到递归到叶子节点。

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