在算法分析中，主定理（英语：master theorem）提供了用渐近符号表示许多由分治法得到的递推关系式的方法。

假设有递推关系式

[
T(n) = atimes T(frac{n}{b}) + f(n)
]

其中:

• (n) 为问题规模
• (a) 为递推的子问题数量，(a>0)
• (frac{n}{b}) 为每个子问题的规模（假设每个子问题的规模基本一样）, (b>0)
• (f(n)) 为递推以外进行的计算工作

则：

1. 若 (existsepsilon > 0, f(n)=O(n^{log_{b}a - epsilon})) (即 (f(n)=o(n^{log_{b}a})))

[
T(n)=Theta(n^{log_{b}a})
]

2. 若 (f(n)=Theta(n^{log_{b}a}))

[
T(n)=Theta(n^{log_{b}a}log_{}n)
]

3. 若 (existsepsilon > 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))是(nlog_{}{n}) 时，虽然可以比出大小，那由于不是多项式级的差距，所以不能适用于主定理。

2. 使用

1. 计算 (n^{log_{b}a})
2. 将 (f(n)) 与 (n^{log_{b}a}) 进行比较
3. 得出结论

3. 举例

分析一下算法复杂度

1
2
3
4
5
6
7
8
9
10
11

int (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}
]