在分析算法的时候，我们经常需要分析递归算法的时间复杂度。

一、主定理(Master Theorem)

主定理适用于求解如下递归式算法的时间复杂度：

其中：

• n 是问题规模大小；
• a 是原问题的子问题个数；
• n/b 是每个子问题的大小，这里假设每个子问题有相同的规模大小；
• f(n) 是将原问题分解成子问题和将子问题的解合并成原问题的解的时间。

对上面的式子进行分析，得到三种情况：

二、应用举例