我何时可以使用主定理？

主定理适用于形式为 T(n) = aT(n/b) + f(n) 的递归关系，其中 a >= 1 且 b > 1，每个层级将问题分割成 a 个大小为 n/b 的子问题。对于不均匀分割、子问题大小可变或非多项式合并成本的递归关系，可能需要使用递归树法、替换法或 Akra-Bazzi 方法。

为什么归并排序的递归关系会给出 O(n log n)？

归并排序产生 T(n) = 2T(n/2) + O(n)：两个半大小的子问题加上线性合并。在这里，递归树所有 log n 个层级的每层工作量相同，因此总工作量是 n 乘以 log n，主定理证实其为 Theta(n log n)。

递归关系用算法在较小输入上的运行时间来表示其在当前输入上的运行时间；求解递归关系可以得到用于分析分治法及其他递归算法的闭式渐近界。

用 PaperMind 寻找选题即将推出Find papers & topics

Tools & resources

Learn & explore

视频即将推出

递归关系是一个方程，它根据函数在较小输入上的值来定义函数在某个输入上的值；在算法分析中，它根据算法在较小子问题上的成本来表示算法在大小为 n 的输入上的成本。

本主题涵盖算法分析中出现的递归关系的建立和求解：替换法、递归树法以及分治递归关系 T(n) = aT(n/b) + f(n) 的主定理。它解释了每种递归算法如何引出递归关系，以及如何将该递归关系转换为大Theta界。本主题不包括渐近符号本身（单独处理）以及离散数学中的组合生成函数方法。

主定理: 对于分治递归关系 T(n) = aT(n/b) + f(n)，主定理通过比较 f(n) 与 n 的 log 以 b 为底 a 的幂次方，给出渐近解，涵盖了叶子、根或平衡层级占主导地位的三种情况。
递归树法和替换法: 递归树法通过累加递归每个层级所做的工作来推导一个界限，然后替换法通过归纳法严格证明该界限；它们共同处理超出主定理范围的递归关系。

求解递归关系是确定递归算法运行时间的标准途径，从归并排序和快速排序到快速乘法以及许多动态规划。工程师和研究人员通常使用主定理来推导和证明这些算法的渐近复杂度声明。

算法的递归分析在高德纳的《计算机程序设计艺术》中得到了系统化。主定理通过 CLRS 成为教科书中的主要内容，而 Akra-Bazzi 方法（1998 年）将其推广到更广泛的不均匀分割的分治递归关系。

我何时可以使用主定理？: 主定理适用于形式为 T(n) = aT(n/b) + f(n) 的递归关系，其中 a >= 1 且 b > 1，每个层级将问题分割成 a 个大小为 n/b 的子问题。对于不均匀分割、子问题大小可变或非多项式合并成本的递归关系，可能需要使用递归树法、替换法或 Akra-Bazzi 方法。
为什么归并排序的递归关系会给出 O(n log n)？: 归并排序产生 T(n) = 2T(n/2) + O(n)：两个半大小的子问题加上线性合并。在这里，递归树所有 log n 个层级的每层工作量相同，因此总工作量是 n 乘以 log n，主定理证实其为 Theta(n log n)。