1. 描述
在算法分析中，主定理（英语：master theorem）提供了用渐近符号表示许多由分治法得到的递推关系式的方法。
假设有递推关系式
\[ T(n) = a\times T(\frac{n}{b}) + f(n) \]
其中:
- \(n\) 为问题规模
- \(a\) 为递推的子问题数量，\(a>0\)
- \(\frac{n}{b}\) 为每个子问题的规模（假设每个子问题的规模基本一样）, \(b>0\)
- \(f(n)\) 为递推以外进行的计算工作
则：
- 若 \(\exists\epsilon > 0, f(n)=O(n^{\log_{b}a - \epsilon})\) (即 \(f(n)=o(n^{\log_{b}a})\))
\[ T(n)=\Theta(n^{\log_{b}a}) \]
- 若 \(f(n)=\Theta(n^{\log_{b}a})\)
\[ T(n)=\Theta(n^{\log_{b}a}\log_{}n) \]
- 若 \(\exists\epsilon > 0,f(n)=O(n^{\log_{b}a +\epsilon})\)(即\(f(n)=\omega (n^{\log_{b}a})\)), 且对于 \(\forall c<1\)，\(n\) 足够大，有 \(aT(\frac{n}{b}) < cf(n)\)
\[ T(n)=\Theta(f(n)) \]
但是要注意，这里大于必须是多项式的大于。比如如果说 \(n^{\log_{a}{b}}\) 是 \(n\) 而 \(f(n)\)是\(n\log_{}{n}\) 时，虽然可以比出大小，那由于不是多项式级的差距，所以不能适用于主定理。
2. 使用
- 计算 \(n^{\log_{b}a}\)
- 将 \(f(n)\) 与 \(n^{\log_{b}a}\) 进行比较
- 得出结论
3. 举例
分析一下算法复杂度 1
2
3
4
5
6
7
8
9
10
11//二分递归求数组之和,范围[low, high]
int Sum(int array[], int low, int high)
{
if (low == high)
{
return array[low];
}
int mid = (low + high) >> 1;
return Sum(array, low, mid) + Sum(array, mid, high);
}
分析:
\[ \begin{aligned} & \text{可知}\ T(n) = 2T(\frac{n}{2}) + O(1),\ a= 2,\ b = 2\\ & \therefore n^{\log_{b}a} = n\\ & f(n)=O(1)= o(n)\\ & \therefore T(n) = \Theta(n) \end{aligned} \]