递归树求解递归方程

在这里插入图片描述

首先了解一下这个递归式 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(nd)

  • 若 a=bd , T(n)=O(ndlog(n))

  • 若 a<bd , T(n)=O(nd)

  • 若a>bd , T(n)=O(nlogb(a))

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

a>bd 【4>21】

所以 T(n)=O(nlogb(a)) 【T(n)=O(nlog2(4)) 】

=O(n2)

方法二：递归树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

根据上图，首先画出递归式 T(n)=4T(n/2)+n 的递归树：
在这里插入图片描述

  • 该树长度为 log2n

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

  • 图中所有节点之和为：

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

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