为什么归并排序是O(n log n)？

归并排序将数组分成两半（log n个递归级别），并且在每个级别上对所有元素进行线性时间合并，从而得到递推关系T(n) = 2T(n/2) + O(n)，主定理将其解为O(n log n)。

快速排序是分治算法吗，即使它没有明确的合并步骤？

是的。快速排序通过围绕枢轴进行分区，在分解步骤中完成其主要工作；一旦两个分区被递归排序，就不需要合并工作。该范式允许大部分工作落在三个阶段中的任何一个。

分治法是一种算法设计范式，它通过将问题分解为相同类型的更小子问题，递归地解决这些子问题，然后将它们的解组合起来，从而得到原问题的解。

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

Tools & resources

Learn & explore

视频即将推出

分治算法递归地将一个问题分解为两个或多个相同或相关类型的子问题，直到子问题足够简单可以直接解决，然后将子问题的解组合起来，以产生原问题的答案。

本主题涵盖了分治算法的三步结构（分解、解决、合并）、典型示例（如归并排序、快速排序、二分查找以及快速整数和矩阵乘法），以及基于递推关系对其运行时间进行的分析。它与主定理和用于分析此类算法的递推关系求解技术密切相关。

递推关系的主定理: 主定理通过比较递归子问题的成本与合并成本f(n)，给出了形如T(n) = aT(n/b) + f(n)的分治递推关系的封闭形式渐近解。
通过分解实现次二次乘法: 递归地拆分操作数并减少递归乘法的次数（如卡拉楚巴乘法和施特拉森矩阵乘法中所示），可以产生比朴素的二次和三次方法渐近更快的算法。

分治法是许多最广泛部署算法的基础：标准库中高效的排序算法（归并排序、快速排序）、查找例程中的二分查找、信号和图像处理中的快速傅里叶变换，以及密码学和任意精度算术中使用的快速乘法。

归并排序归功于约翰·冯·诺依曼（1945年）。C. A. R. Hoare于1962年发表了快速排序。卡拉楚巴1960年的次二次乘法和施特拉森1969年的矩阵乘法算法表明，递归分解可以超越经典界限，有助于将分治法确立为一种基础范式。

为什么归并排序是O(n log n)？: 归并排序将数组分成两半（log n个递归级别），并且在每个级别上对所有元素进行线性时间合并，从而得到递推关系T(n) = 2T(n/2) + O(n)，主定理将其解为O(n log n)。
快速排序是分治算法吗，即使它没有明确的合并步骤？: 是的。快速排序通过围绕枢轴进行分区，在分解步骤中完成其主要工作；一旦两个分区被递归排序，就不需要合并工作。该范式允许大部分工作落在三个阶段中的任何一个。