主定理

主定理

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

其中：

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

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