Question

递归树求解递归方程T(n)=8T(n/2)+n^2

Answer 1

问：递归树求解递归方程T(n)=8T(n/2)+n^2

答：亲您好，这个递归方程的时间复杂度可以用递归树来分析。首先，设解决一个大小为 n 的问题的时间复杂度为 T(n)。对于一个大小为 n 的问题，我们需要分成两个大小为 n/2 的子问题，然后分别解决它们，这将需要 2T(n/2) 的时间。

答：此外，还需要进行一些其他的计算，时间复杂度为 n^2，因此总时间复杂度为：T(n) = 2T(n/2) + n^2这个递归方程可以用递归树来表示，每一层表示解决大小为 n 的问题所需的时间复杂度。通过递归树的分析，我们可以发现，总时间复杂度是 O(n^2 log n)。

问：答案是O（n＾3）呀

答：首先，画出递归树。在递归树中，每个节点表示递归调用的一个实例，其深度表示递归的层数，每个节点的代价表示该实例的计算代价。在该问题中，每次递归调用的代价为 n^2，每次递归调用的规模为原来的一半。在递归树中，第 i 层的代价为 (n/2^i)^2，该层的节点数为 8^i。因此，第 i 层的总代价为 8^i * (n/2^i)^2。为了求解递归方程的渐进解，我们需要求出递归树的总代价。递归树的总共有 log(n) 层，因此我们可以将每层的代价相加，得到：T(n) = sum(i=0 to log(n)-1) [ 8^i * (n/2^i)^2 ]接下来，我们可以化简这个式子：T(n) = sum(i=0 to log(n)-1) [ 2^(3i) * n^2 ] = n^2 * sum(i=0 to log(n)-1) [ 2^(3i) ] = n^2 * (2^(3*log(n))-1)/(2^3-1) （等比数列求和公式） = O(n^3)因此，递归方程的渐进解为 T(n) = O(n^3)。