主定理

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

假设有递推关系式

有

其中， 为问题规模， 为递归的子问题数量， 为每个子问题的规模（假设每个子问题的规模基本一样）， 为递归以外进行的计算工作。