递归

Master 公式

适用范围为子过程规模相等的情况，否则不适用。

$T(N)=a\ast T(\frac{N}{b})+O(N^d)$

• a: 子问题被调用的次数

• N：为母问题规模，本程序的母问题规模为 N

• $$T(N/B):\mathrm{子}\mathrm{问}\mathrm{题}\mathrm{规}\mathrm{模}，\mathrm{本}\mathrm{程}\mathrm{序}\mathrm{的}\mathrm{子}\mathrm{问}\mathrm{题}\mathrm{规}\mathrm{模}\mathrm{为}：N/2（\mathrm{二}\mathrm{分}）；$$
• $$O(n^d)：\mathrm{子}\mathrm{问}\mathrm{题}\mathrm{以}\mathrm{为}\mathrm{的}\mathrm{时}\mathrm{间}\mathrm{复}\mathrm{杂}\mathrm{度}，\mathrm{本}\mathrm{程}\mathrm{序}\mathrm{为}O(N^1)$$

满足如上公式的程序都可以根据 master 公式计算时间复杂度：

1. $$\$log(b,a)>d:\mathrm{复}\mathrm{杂}\mathrm{度}\mathrm{为}O（N^{l}og(b,a)$$
2. $$log(b,a)<d:\mathrm{复}\mathrm{杂}\mathrm{度}\mathrm{为}O（N^d）$$
3. $$log(b,a)=d:\mathrm{复}\mathrm{杂}\mathrm{度}\mathrm{为}O（N^d\ast logN）$$