Master 公式

什么是 Master 公式

用来求解子问题等规模的递归行为的算法的时间复杂度的一种方法

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

其中，$T(N)$表示母问题的规模是$N$，$T(\frac{N}{b})$表示子问题的规模为$\frac{N}{b}$（即子问题必须等规模），$a$表示调用子问题的次数，而$O(N^d)$表示除去子问题后，剩下的部分时间复杂度为$O(N^d)$

满足 Master 公式的递归行为，其时间复杂度计算如下

$$\begin{array}{rl}\text{if}& lo{g}_{b}a<dO(N^d)\\ \text{if}& lo{g}_{b}a>dO(N^{lo{g}_{b}a})\\ \text{if}& lo{g}_{b}a=dO(N^{d}logN)\end{array}$$

举几个例子

示例代码

• 在上图问题中，母问题的规模是$T(N)$，子问题的调用是相等的，即$T(\frac{N}{2})$。
• 子问题调用了两次，除了子问题调用之外，剩下的语句复杂度是$O(1)$

综上，$a=2,b=2,d=0$,因此其 Master 公式为 $T(N)=2\times T(\frac{N}{2})+O(N^0)$，进而我们计算出其时间复杂度为 $O(N)$

继续上图的算法，如果上问题中 process 函数中，调用自身时是计算左侧2/3的最大值和右侧1/3的最大值，那么本问题就不满足Master公式，因为其子问题的规模不是相等的。

图中部分代码说明

如果使用mid=(L+R)/2来求中点，可能会导致溢出。因此可以写成mid=L+(R-L)/2，这样一定保证不会溢出。而上图中>>1（右移一位）就等同于其除以2了，而且直接右移一位比除2要快。