算法（15）：sorting complexity-6.3

这一节的名字叫“排序复杂度Sorting Complexity”但它实际上在回答一个更根本的问题“只靠比较大小来排序最快能有多快有没有可能比归并排序更快”结论归并排序在“比较次数”上已经是最优的但为了理解为什么我们需要把“算法运行时间”和“物理极限”分开看。1. 三组核心定义先锁死术语计算模型Model of Computation允许算法执行哪些操作。在排序问题中我们限定为基于比较Compare-based的模型——你只能通过a b来获取两个元素相对顺序的信息不能直接读取元素的内存地址来推算它的大小比如不能像基数排序那样按位拆数字。上界Upper Bound某个已知算法在最坏情况下需要的操作次数。例如归并排序能保证最多~ N log₂ N次比较所以“排序问题的上界是N log₂ N”。下界Lower Bound任何算法包括还没被发明出来的在最坏情况下都不可能少于这个次数。它是对问题本身难度的证明。如果上界 下界在常数因子范围内这个算法就是这个问题在对应成本模型下的最优算法Optimal Algorithm。2. 为什么比较排序的下界是~ N log₂ N想象你对N个互不相同的元素进行排序。你只能靠比较a[i]和a[j]来判断它们的顺序。物理事实输入有N!种可能的排列例如 3 个元素有 6 种排列4 个元素有 24 种。每一次比较最多只能产生两种结果小于或大于等于。因此每次比较最多只能把“可能的排列数量”分成两半。为了区分出N!种不同的排列你至少需要做log₂(N!)次比较。根据斯特林公式Stirlings formulalog₂(N!) ≈ N log₂ N。这意味着任何基于比较的排序算法在最坏情况下都不可能少于N log₂ N次比较。比较次数必然大于Nlog2N以最坏情况为标准否则比较无意义。避免一次就比出来的情况3. 结合归并排序看这张图你已经知道归并排序的最坏情况比较次数就是~ N log₂ N。现在把这个结论和刚学的下界合在一起看下界证明说“无论你怎么设计都不可能少于N log₂ N次比较。”归并排序说“我能做到N log₂ N次比较。”所以在“比较次数”这个成本模型下归并排序已经是最优的不可能再被超越了。这就是为什么 PPT 会说Optimal algorithm mergesort。4. 这个“最优”的局限性“最优”只适用于比较次数不是“所有资源”。归并排序的空间成本它需要额外的aux数组N个额外空间所以它不是“空间最优”。存在原地排序算法如堆排序但它们的常数因子通常比归并排序大。如果允许不同操作模型如果你不是只靠比较而是利用键的物理表示比如知道输入是 32 位整数你可以使用基数排序Radix Sort它在某些情况下能达到O(N)时间突破N log N的限制。但这是因为你换了计算模型而不是解决了比较排序的极限。5. 对你目前学习的意义这一节的作用是告诉你当你在归并排序和快速排序之间选择时你不再需要担心“有没有可能发明一个比归并排序更快的基于比较的通用排序算法”——因为数学上已经证明了不存在。你能优化的只有常数因子、内存使用和缓存行为。现在你已经知道了归并排序的理论天花板在哪里下一节快速排序出现时你就能直接看到它在实践层面缓存、原地性如何与理论最优的归并排序形成对比。如果你准备好进入快速排序Quicksort可以继续推进。