递归树求解递归方程

首先了解一下这个递归式 T(n)=4T(n/2)+n 是什么意思：

• 4表示我们将一个问题分解为 4 个子问题
• n/2表示每个子问题的规模是原问题的 1/2
• n表示合并需要的额外计算时间

方法一可用主定理【Master定理】

主定理【Master定理】提供了分治方法带来的递归表达式的渐进复杂度分析。

将规模为 n 的问题通过分治，得到 a 个规模为 n/b 的问题，每次递归带来的额外计算为 c(n^d)

即 T(n)=a(n/b)+c(n^d)

• 若 a=b^d , T(n)=O(n^dlog(n))

• 若 ad , T(n)=O(n^d)

• 若a>b^d , T(n)=O(n^logb(a))

该题 a=4，b=2，c(n^d)=n → d=1

a>b^d 【4>2¹】

所以 T(n)=O(n^logb(a)) 【T(n)=O(n^log2(4)) 】

=O(n²)

方法二：递归树

根据上图，首先画出递归式 T(n)=4T(n/2)+n 的递归树：

• 该树长度为 log₂n

  • 因为原本的问题规模为 n ,到了树的最底层，为 1 了，也就是说，每次往下一层，规模变为 1/2，假设它变成 i 个节点，则 n / 2ⁱ = 1 ，即 n = 2ⁱ ，所以 i = log₂n

• 图中所有节点之和为：

n+2n+4n+8n+16n+…(2ⁱ)n = (1+2+4+…+2ⁱ)n
根据等比数列求和公式可得：
1*(1-2ⁱ)/(1-2) = 2ⁱ-1
因为i=log₂n
所以2^(log₂n) - 1

所以图中所有节点之和为：n(n-1)=n²-n
所以时间复杂度为O(n²)