笔记: 算法分析 03

2026-09-29 算法分析笔记
算法分析CS笔记

排序问题很适合用来观察一件重要的事: 算法的改进往往不是把同一个循环写得更快, 而是改变问题的组织方式.

选择排序, 冒泡排序和插入排序都很直观. 但当输入规模增大时, 它们大多需要二次量级的工作. 归并排序第一次让我们看到, 只要愿意把问题递归地拆开, 排序可以稳定地做到 . 快速排序则进一步说明, 同样是分治, 划分是否均衡会直接决定递归的效率.

这一节还要回答一个更根本的问题: 只是目前已知算法的水平, 还是比较排序本身无法突破的极限?

1. 简单排序与平均情况分析

前文已经系统讨论了最好、最坏与平均情况, 以及选择排序、冒泡排序和插入排序的复杂度. 这里不再重复推导, 只保留后文需要使用的结论.

除非特别说明, 本课程所说的运行时间默认指最坏情况运行时间. 平均情况则必须先指定输入的概率分布; 对本节涉及的排序分析, 一个典型假设是: 个互异元素的 个排列等概率出现.

对前面三种简单排序,

特别地, 对均匀随机排列, 插入排序第 次插入的位置在 中等概率出现, 从而平均总比较次数为

这段分析中最值得保留的方法是: 先根据随机输入确定某个局部状态的概率分布, 再对不同状态下的代价取期望. 后面分析快速排序的平均复杂度时, 我们会再次使用完全相同的思路.

2. 归并排序: 先拆开, 再合起来

前面的简单排序都在原数组上逐步修补顺序. 归并排序换了一个角度: 如果两个较小的数组已经分别排好序, 能否很快把它们合成一个有序数组?

答案是可以, 而且只需要线性时间. 这正是整个算法成立的关键.

Definition 1 (分治的三个步骤)

一个典型的分治算法在每一层递归中做三件事:

  • Divide: 把原问题分成若干个规模更小, 类型相同的子问题.
  • Conquer: 递归地解决这些子问题; 当规模足够小时直接求解.
  • Combine: 把各个子问题的解合成为原问题的解.

归并排序几乎是这个范式最直接的实现. 对区间 ,

  1. 取中点 .
  2. 递归排序 .
  3. 递归排序 .
  4. 把两个有序区间合并.

当 时, 区间至多包含一个元素, 已经有序, 递归停止.

MergeSort(A, p, r)
    if p >= r
        return
    q = floor((p + r) / 2)
    MergeSort(A, p, q)
    MergeSort(A, q + 1, r)
    Merge(A, p, q, r)

2.1 合并两个有序区间

设 与 已分别有序. 用两个指针分别指向两段当前还没有处理的最左元素, 每次比较这两个元素, 把较小者写入辅助数组 .

Merge(A, p, q, r)
    i = p
    j = q + 1
    k = p

    while i <= q and j <= r
        if A[i] <= A[j]
            B[k] = A[i]
            i = i + 1
        else
            B[k] = A[j]
            j = j + 1
        k = k + 1

    copy the remaining elements to B
    copy B[p..r] back to A[p..r]

这个过程为什么正确? 因为在任意时刻, 两个子数组中还没有处理的最小元素, 必然分别位于两个指针的位置. 因而全局最小的未处理元素, 一定就是这两个元素中的较小者.

也可以把它写成一个循环不变式:

> 在写入 之前, 恰好包含两个输入子数组中最小的 个元素, 且已经按非降序排列.

每次取两个当前首元素中的较小者, 正好把下一个全局最小元素接到末尾, 因而不变式保持成立. 当其中一段耗尽后, 另一段剩余部分本身已经有序, 直接整体复制即可.

若本次合并的总元素个数为

则比较次数介于约 与 之间, 再加上把元素写入 以及复制回 的线性工作, 因而

课件采用一个全局辅助数组 . 它可以在整个递归过程中反复复用, 不需要在每一层重新申请一份长度为 的数组. 因而归并排序的额外空间为 , 而不是 .

2.2 为什么总时间是

设 为归并排序规模为 的输入所需时间. 忽略奇偶性带来的取整差异, 有

递归树给出了最直观的解释.

图中节点标出子问题规模, 右侧标出该层的合并工作量. 省略的后续层继续二分, 直到每个子问题只剩一个元素; 若 不是 2 的幂, 两个子问题的规模相差至多 1.

因此共有 层, 每一层总工作量都是 , 从而

Theorem 2 (归并排序的时间与空间复杂度)

归并排序在最好, 平均和最坏情况下的时间复杂度均为

使用课件中的辅助数组实现时, 额外空间复杂度为

归并排序几乎不关心原数组是否已经有序. 它的递归结构和合并过程基本不会因为输入顺序不同而消失, 因而三种情况下具有相同的渐近时间复杂度.

3. 快速排序: 先让一个元素就位

归并排序先把问题对半拆开, 等两个子问题解决后再合并. 快速排序的思路恰好相反: 先用一个主元把数组划分, 再递归处理两边.

设当前区间为 , 取最后一个元素

作为主元. 扫描其余元素, 把小于 pivot 的元素搬到左侧, 其余元素留在右侧. 扫描结束后, 再把 pivot 放到两块区域之间.

QuickSort(A, p, r)
    if p >= r
        return

    pivot = A[r]
    i = p

    for j = p to r - 1
        if A[j] < pivot
            swap A[i] and A[j]
            i = i + 1

    swap A[i] and A[r]

    QuickSort(A, p, i - 1)
    QuickSort(A, i + 1, r)

3.1 Partition 到底保证了什么

扫描指针为 , 左侧小元素区域的边界为 . 在每次处理 之前, 可以保持以下不变式:

而 尚未处理, 仍是主元.

若 , 就把它与 交换, 再把 右移一格. 若 , 则只需继续扫描.

扫描结束时,

此时交换 与 , 得到

于是主元已经处在整个区间排序完成后应处的最终位置. 重要的是, 只有主元的位置被确定了, 左右两块内部仍可能完全无序, 所以还要继续递归.

一次划分只做一趟线性扫描, 所以规模为 的 partition 需要 时间.

4. 快速排序为什么有时快, 有时慢

归并排序每次固定地把数组大致平分. 快速排序的子问题规模则由主元最终落在哪里决定. 因此它的复杂度本质上取决于划分是否均衡.

4.1 最好情况

若每次主元都恰好把区间分成大小近似相等的两部分, 则

递归深度为 , 每层所有 partition 的总工作量为 , 因而

4.2 最坏情况

若每次主元都是当前区间的最小值或最大值, 则一侧为空, 另一侧只减少一个元素:

展开得到

例如, 当每次取最后一个元素为主元时, 已经严格递增的数组会让主元始终成为最大元素. 对本节使用的严格 < pivot 划分而言, 全相等数组也会产生同样的退化.

这说明“分治”三个字本身并不会自动带来高效率. 如果 Divide 根本没有把问题有效缩小, 递归就会退化成近似双重循环.

4.3 平均情况

现在假设输入是 个互异元素的均匀随机排列. 最后一个元素作为主元时, 它在整个数组中的秩等概率地取 .

令 表示快速排序对 个元素所做的平均比较次数. 若主元最终位于第 个位置, 则左右子问题规模分别为 与 , 而当前 partition 恰好进行 次主元比较. 因而

利用左右两项的对称性,

这个递推式包含此前所有 . 一个很有用的技巧是把相邻两式相减来消掉求和.

先乘以 :

对 有

两式相减,

整理为

从 开始展开, 可以得到

其中

因此

Theorem 1 (快速排序的平均比较次数)

对 个互异元素的均匀随机排列, 使用末元素为主元的快速排序平均进行

次比较, 因而平均时间复杂度为

这里的概率假设非常重要. “平均为 ”并不意味着每一个输入都接近这一复杂度, 它只描述给定随机模型下的期望.

4.4 空间复杂度

快速排序通常直接在原数组上交换元素, 不需要归并排序那样的长度为 的辅助数组. 但递归调用栈仍然需要空间.

因此“原地排序”并不等于“完全不需要额外空间”.

4.5 为什么实践中快速排序常常很快

归并排序拥有稳定的 最坏时间, 但快速排序在数组上常常仍具有很好的实际表现. 主要原因包括:

实际实现还会进一步降低退化风险. 常见策略包括随机选择主元, 采用更稳健的主元估计, 对很小的子数组改用插入排序. 一类典型的混合算法会在递归过深时切换到具有 最坏保证的排序算法; introsort 的经典做法是切换到堆排序.

这也说明一个重要区别: 渐近最优并不等于在每台机器和每个输入规模上都最快.

5. 比较排序能否突破

归并排序已经把最坏时间做到 . 一个自然的问题是: 能不能继续设计出一个最坏时间为 的比较排序?

要回答这个问题, 需要暂时抛开某个具体算法, 研究“只通过比较获得次序信息”这件事本身最多能有多高效.

Definition 1 (比较排序)

若一个排序算法只能通过比较输入元素之间的大小关系来获取它们的相对次序信息, 则称它为比较排序.

插入排序, 选择排序, 冒泡排序, 归并排序和快速排序都属于比较排序.

为了研究下界, 假设 个输入元素两两不同. 每次比较只有两种可能结果, 例如

或

于是任何一个确定性的比较排序都可以抽象成一棵二叉决策树:

下面以三个互异元素为例, 展示一棵完整的比较决策树. 分支上的“是”和“否”表示当前比较是否成立, 每个叶子中的元素按递增次序列出.

这棵树有 个可达叶子. 有些输入经过 2 次比较便到达叶子, 最长路径则需要 3 次比较, 所以树高为 3.

考虑有个互异元素情况, 因为输入元素互不相同, 它们共有

种可能的相对排列. 一个正确的比较排序必须能够区分所有这些情况, 所以决策树至少需要 个可达叶子.

设树高为 , 即从根到叶子最多经过 条边. 高度为 的二叉树至多有 个叶子. 每个节点最多产生两个孩子. 将提前结束的分支补齐到深度 , 叶子数只会增加或保持不变, 而补齐后的树至多有 个叶子. 结合排序需要区分的排列数, 得到

取以 2 为底的对数,

而

所以

由此得到比较排序最核心的下界.

Theorem 2 (比较排序的最坏情况时间下界)

任意基于比较的排序算法, 在最坏情况下都至少需要

次比较.

Proof

比较排序可以表示成二叉决策树. 对 个互异元素, 正确算法必须区分全部 种排列, 因而决策树至少有 个可达叶子.

若树高为 , 二叉树至多有 个叶子, 所以 . 因而

而树高正是某个输入所经历的最大比较次数, 即最坏情况比较次数.

归并排序的最坏复杂度为 , 与这个下界相匹配. 因而在比较排序这一模型内, 它已经达到渐近最优的最坏情况数量级.

快速排序的平均复杂度同样是 , 但它的最坏情况仍可能达到 .

课件还提出了一个有趣的问题: 比较排序的决策树中, 最浅的叶子能有多浅?

答案是至少 次比较. 直观上, 把每个元素看成一个顶点, 每次比较在两个元素之间连一条边. 若比较少于 次, 这个图不可能连通, 至少有两组元素之间从未通过比较建立任何次序联系, 因而还不足以唯一确定所有元素的完整排序. 插入排序在已经有序输入上的 次比较正好达到这一界.

6. 从排序中抽象出分治法

现在回头看归并排序与快速排序, 可以发现它们虽然都叫分治, 但“难点”落在不同位置.

归并排序的 Divide 很简单: 直接从中间切开. 真正关键的是 Combine, 即如何在线性时间内合并两个有序子数组.

快速排序则几乎不需要 Combine. 它的关键在 Divide: partition 必须把主元放到最终位置, 并希望得到足够均衡的左右子问题.

因此, 设计分治算法时不能只写出“递归处理左右两半”. 更重要的问题始终是:

若一个规模为 的问题被分成 个规模约为 的子问题, 而分解和合并额外花费 , 常常会得到形如

的递推式. 归并排序就是其中最基本的例子:

后续课程会继续研究如何系统求解这类递推式.

7. 下一步: 最大子数组问题

本节最后开始引出分治法的下一个应用.

设数组

记录某个量逐步发生的变化. 我们希望找到一个连续区间 , 使区间和最大:

在股票价格的语境中, 可以把 理解为相邻两天之间的价格变化. 选择一个连续区间, 就对应选择买入与卖出的时间段; 最大连续区间和对应最大的累计收益.

直接枚举所有区间当然可以解决问题, 但这还没有利用分治的结构. 下一节将继续研究: 如何把“最大子数组”拆成更小的同类问题, 以及跨越分界点的最优区间应如何处理.

8. 本节排序算法总览

把本节出现的算法放在一起, 可以看到它们各自交换了什么代价.

这里最重要的并不是背下五行复杂度, 而是理解它们背后的原因:

从这一点开始, 算法学习的重点也逐渐从“实现一个过程”转向“设计问题的结构”.