算法-主定理 - 马育民老师

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

T(n) = aT(\frac{n}{b}) + f(n)

n：问题的规模，即输入数据的大小。例如，在排序算法中，(n) 可能代表要排序的元素数量。
a：子问题数量。换句话说，它表示原始问题被分解成多少个较小的子问题。例如，在二分查找中，每次只产生一个子问题，因此 (a = 1)；而在快速排序或归并排序中，每次递归调用会处理两个子数组，所以 (a = 2)。
b：每个子问题相对于原问题的规模缩小的比例。具体来说，如果原问题是规模为 (n) 的问题，则每个子问题的规模是 (n/b)。例如，在二分查找中，每次递归调用处理的问题规模减半，因此 (b = 2)；同样地，在快速排序或归并排序中，每次递归调用处理的是原问题的一半，所以 (b = 2)。
f(n)：除了递归调用之外的工作量，即非递归部分所需的时间复杂度。这通常指的是合并步骤或处理当前层任务所需的额外时间。例如，在归并排序中，(f(n) = O(n))，因为合并两个已排序数组需要线性时间。

a≥1，b>1为常数，f(n) 为函数，T(n) 为非负整数。则有以下结果（分类讨论）：