算法-主定理 作者：马育民 • 2025-05-12 23:27 • 阅读：10002 主定理适用于求解如下递归式算法的时间复杂度： $$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) 为非负整数。则有以下结果（分类讨论）： [](https://www.malaoshi.top/upload/0/0/1GW176CWLTwj.png) 参考： https://baike.baidu.com/item/%E4%B8%BB%E5%AE%9A%E7%90%86/3463232 https://www.luogu.com.cn/article/w3avh1ku https://zhuanlan.zhihu.com/p/113406812 原文出处：http://malaoshi.top/show_1GW176Ck6osk.html