COURSE NOTES / DAY 04

算法设计与分析 Day4:随机快速排序、排序下界与三道作业详解

RedMoon · 算法设计与分析 · Day4

快速排序的一次划分会把枢轴放到最终位置。剩下的工作量,取决于枢轴两侧各有多少元素。本次课从划分规模出发,推导随机快速排序的期望时间,再结合堆排序、计数排序和决策树,讨论排序算法利用的信息及其复杂度下界。

文末详解三道作业:线性时间最大子数组、用最小堆合并有序表,以及快速排序与插入排序的组合。每题包含题意、算法、执行示例、正确性证明和复杂度分析。

记 lgn=log2n\lg n=\log_2 n,lnn\ln n 为自然对数;区间 A[l..r]A[l..r] 包含两端。Python 代码使用 0-based 下标,返回的最大子数组区间也包含左右端点。时间分析默认一次比较、数组访问及机器字范围内的算术运算花费常数时间;涉及输入编码长度时,会单独说明。

一、课堂热身:多数元素为什么可以两两抵消

1. 多数元素与众数的区别

课件第 2 页的题目是 LeetCode 169「多数元素」:给定一个非空数组,保证存在出现次数 严格大于 ⌊n/2⌋\lfloor n/2\rfloor 的元素,找出它。

众数只要求出现次数最多,多数元素则要求占据一半以上。例如 [1,1,2,2,3][1,1,2,2,3] 中,1 和 2 都是众数,但没有多数元素。严格多数至多只有一个,因为两个数的出现次数不可能都超过 n/2n/2。

直接统计频次即可求解。用哈希表记录,期望时间为 O(n)O(n),最坏空间为 O(n)O(n);若已知整数值域为 1..K1..K,也可以使用长度为 KK 的计数数组,时间为 O(n+K)O(n+K),空间为 O(K)O(K)。值域越大,初始化计数数组的成本越高。

2. Boyer–Moore 投票法

从数组中删去两个值不同的元素,原来的多数元素仍然是剩余数组中的多数元素。

设多数元素为 xx,原来出现 c>n/2c>n/2 次。若删去的一对中包含 xx,它还剩 c−1c-1 次,且 c−1>(n−2)/2c-1>(n-2)/2;若这一对都不是 xx,它的次数不变,占比反而更高。因此,不断抵消后留下的候选值就是 xx。

实现时维护一个候选值 candidate 和未被抵消的数量 count:

def majority_element(a):
    if not a:
        raise ValueError("input must be nonempty")
    candidate, count = None, 0
    for x in a:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

以 [2,2,1,1,1,2,2][2,2,1,1,1,2,2] 为例:

下标 读入值 处理后的候选值 count 发生的操作
0 2 2 1 空状态建立候选值
1 2 2 2 同值累积
2 1 2 1 抵消一对不同值
3 1 2 0 当前候选全部抵消
4 1 1 1 重新建立候选值
5 2 1 0 再次抵消
6 2 2 1 剩下候选值 2

count 记录尚未被抵消的候选数量,不代表候选值在整个数组中的出现次数。算法只扫描一次,时间 Θ(n)\Theta(n),辅助空间 O(1)O(1)。

若题目不保证多数元素存在,还需在第二遍扫描中统计候选值,检查它是否出现超过 ⌊n/2⌋\lfloor n/2\rfloor 次。例如 [1,2,3][1,2,3] 第一遍也会产生候选值,但数组中没有多数元素。

二、分治排序:归并排序与快速排序的分工

排序的输出既要按非降序排列,也要与输入包含完全相同的元素及重复次数。正确性证明需要同时覆盖有序性与元素保留,避免遗漏或增加元素。

课堂先区分了问题、算法和分析。排序规定要解决什么问题,归并排序与快速排序给出具体做法,正确性和运行时间分析则回答这些做法是否正确、需要多少代价。同一个问题可以有多种算法,分析时也可以采用不同模型。

分治环节 归并排序 快速排序
边界 长度不超过 1 时返回 长度不超过 1 时返回
分 按下标切成两半,切分本身简单 扫描元素,按枢轴值划分
治 排序左右两半 排序枢轴两侧
合 线性合并两个有序区间 枢轴已经就位,无须再线性合并
子问题规模 两侧约为 n/2n/2 可能从 0,n−10,n-1 到接近均分

归并排序的主要线性工作在合并阶段,快速排序则在划分阶段。分析快速排序时,需要继续考察划分后两个子问题的规模。

三、随机快速排序:划分与实现

1. 枢轴必须退出后续递归

先从数组中均匀随机选取一个位置,以该位置的元素为枢轴 xx。单独取出这次出现,再将其余元素分成:

B={a:a≤x},C={a:a>x}. B=\{a:a\le x\},\qquad C=\{a:a>x\}.

递归结果为:

sort(B)+[x]+sort(C). \operatorname{sort}(B)+[x]+\operatorname{sort}(C).

这里的加号表示顺序拼接。枢轴本身不再进入 BB 或 CC,所以两侧规模之和是 n−1n-1,每个递归子问题都严格变小。

数组含重复值时,也必须排除选作枢轴的这次出现。否则,把枢轴放回「小于等于」的一侧后,全相等数组可能原样进入下一次递归,无法结束。原地划分会固定一个枢轴位置,使后续区间严格缩小。

2. 原地划分的四个区域

课件第 8 页使用 Lomuto 划分。先把随机选中的枢轴换到 A[r]A[r],令 x=A[r]x=A[r],再扫描 A[p..r−1]A[p..r-1]。

循环每次开始时维护:

区域 语义
A[p..i]A[p..i] 已处理且全部 ≤x\le x
A[i+1..j−1]A[i+1..j-1] 已处理且全部 >x>x
A[j..r−1]A[j..r-1] 尚未检查
A[r]A[r] 暂存枢轴 xx

若 A[j]≤xA[j]\le x,先令 ii 加 1,再交换 A[i]A[i] 与 A[j]A[j],把这个元素纳入左区间;若 A[j]>xA[j]>x,则直接推进扫描位置。

扫描结束后,交换 A[i+1]A[i+1] 与 A[r]A[r]。令 q=i+1q=i+1,得到:

A[p..q−1]≤A[q],A[q+1..r]>A[q]. A[p..q-1]\le A[q],\qquad A[q+1..r]>A[q].

from random import Random


def randomized_partition(a, p, r, rng):
    pivot_index = rng.randrange(p, r + 1)
    a[pivot_index], a[r] = a[r], a[pivot_index]
    x = a[r]
    i = p - 1
    for j in range(p, r):
        if a[j] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[r] = a[r], a[i + 1]
    return i + 1


def quicksort(a, rng=None):
    if rng is None:
        rng = Random()

    def sort(p, r):
        if p >= r:
            return
        q = randomized_partition(a, p, r, rng)
        sort(p, q - 1)
        sort(q + 1, r)

    sort(0, len(a) - 1)
    return a

3. 课件示例的交换过程

输入 [40,30,10,20][40,30,10,20],取末尾的 20 为枢轴。使用 0-based 下标,初始 i=−1i=-1:

扫描阶段 比较结果与动作 数组
j=0j=0 40>2040>20,不交换 [40,30,10,20][40,30,10,20]
j=1j=1 30>2030>20,不交换 [40,30,10,20][40,30,10,20]
j=2j=2 10≤2010\le20,令 i=0i=0,交换位置 0 和 2 [10,30,40,20][10,30,40,20]
扫描结束 交换位置 i+1=1i+1=1 和末尾枢轴 [10,20,40,30][10,20,40,30]

返回 q=1q=1。20 已经就位,但右侧 [40,30][40,30] 还没有排序。一次划分只保证枢轴两侧满足大小关系。

4. 正确性与空间

用循环不变式证明划分正确。初始化时,两个已处理区域均为空;扫描中,每次交换将符合条件的元素放进左区间,并保持右区间的性质;扫描结束时,未知区域为空,最后一次交换将枢轴放到两区之间。

再对区间长度归纳,即可证明快速排序正确。长度不超过 1 时,区间已有序。更长的区间经过划分后,枢轴两侧满足大小关系;由归纳假设,两个更短区间递归排序后也各自有序,拼接起来便得到整个有序区间。全过程只交换已有元素,因此输入的多重集合保持不变。

长度为 m=r−p+1m=r-p+1 的划分需要 m−1m-1 次关键字比较,时间 Θ(m)\Theta(m),辅助空间 O(1)O(1)。上面的快速排序仍有递归栈:互异元素、随机枢轴时,期望栈深为 O(logn)O(\log n),最坏可达 O(n)O(n)。若每次只递归较短一侧、用循环处理较长一侧,可以把栈空间最坏限制在 O(logn)O(\log n)。

5. 重复值与稳定性

Lomuto 使用 <= 判断。所有元素相等时,每次划分都把其余 m−1m-1 个元素留在左侧,无论随机选中哪个位置,时间都是 Θ(n2)\Theta(n^2)。随机化改变了枢轴的选择方式,但这个划分规则仍会把所有相等元素放到同一侧。

课件之外,还可以用三路划分处理重复值:将元素分成 <x<x、=x=x、>x>x 三区,只递归两侧;所有值相等时,一次线性扫描即可结束。后续期望递推假设 元素互异,此时每个枢轴秩恰好对应一种左右规模。

这种交换式快速排序通常不稳定。例如给相同键附上标签,[(2,a),(2,b),(1,c)][(2,a),(2,b),(1,c)] 以 1 划分后成为 [(1,c),(2,b),(2,a)][(1,c),(2,b),(2,a)],两个键为 2 的记录已交换先后。

四、输入、随机选择与运行时间

1. 运行时间有两个自变量

记 T(A,R)T(A,R) 为输入数组 AA、随机选择序列 RR 下的运行时间。即使固定 AA,不同的枢轴序列也会产生不同的递归树。

「随机快速排序的期望时间」通常对算法的随机选择取期望:

max|A|=n𝔼R[T(A,R)]. \max_{|A|=n}\mathbb E_R[T(A,R)].

若元素互异,这个期望为 O(nlogn)O(n\log n)。分析时先固定任意输入,再对枢轴的随机选择取平均,无须假设输入本身是随机排列。

平均情况 𝔼A[T(A)]\mathbb E_A[T(A)] 则对输入取平均,需要先给定输入分布。它可能与随机算法的期望时间具有相同的渐近阶,但两者取平均的对象不同。

2. 不带有序性预检查的普通版本

若每次都接近均分:

T(n)=2T(n/2)+Θ(n)=Θ(nlogn). T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n).

若每次都选到当前最小值或最大值:

T(n)=T(n−1)+Θ(n)=Θ(n2). T(n)=T(n-1)+\Theta(n)=\Theta(n^2).

后一种情况下,扫描规模累加为 n+(n−1)+⋯+2n+(n-1)+\cdots+2。随机快速排序也可能连续选到这样的枢轴,因此最坏时间仍为二次量级,未降至 O(nlogn)O(n\log n)。

3. 加入有序性检查后的版本

课件第 11 页另加了一步:先扫描数组,发现已经有序就返回。对这个变体,已排序输入的运行时间是 Θ(n)\Theta(n),因为只需完成一次检查。

带预检查版本在有序输入上花费的时间,与普通快速排序在均衡划分下的 Θ(nlogn)\Theta(n\log n) 对应不同条件。几种情况如下:

所讨论的情况 时间
普通版本,划分始终接近均衡 Θ(nlogn)\Theta(n\log n)
普通版本,划分始终极端不均衡 Θ(n2)\Theta(n^2)
带预检查版本,输入原本有序 Θ(n)\Theta(n)
互异元素的随机版本,对随机枢轴取期望 Θ(nlogn)\Theta(n\log n)

预检查本身需要线性时间。下一节沿用课件的规范化递推,分析不提前返回的普通随机版本。

五、随机快速排序的期望时间推导

1. 按枢轴秩分类

设 T(n)T(n) 为规模 nn 的期望代价。元素互异、从当前子数组均匀选择枢轴时,枢轴可能有 0,1,…,n−10,1,\ldots,n-1 个更小的元素,每种情况概率都是 1/n1/n。

当左侧规模为 ii 时,右侧规模为 n−1−in-1-i。将一次线性处理的代价规范化写成 nn,得到:

T(n)=1n∑i=0n−1(T(i)+T(n−1−i))+n. T(n)=\frac1n\sum_{i=0}^{n-1} \bigl(T(i)+T(n-1-i)\bigr)+n.

两部分求和包含相同的项,只是次序相反,因此:

T(n)=2n∑i=0n−1T(i)+n. T(n)=\frac2n\sum_{i=0}^{n-1}T(i)+n.

若保留具体实现中的常数项和线性项系数,推导方式与渐近阶不变。边界代价 T(0),T(1)T(0),T(1) 均为常数;相邻规模作差时,要从两个递推式都成立的规模开始,再把有限个初值并入常数。

2. 乘以规模,再对相邻式子作差

两边乘以 nn:

nT(n)=2∑i=0n−1T(i)+n2. nT(n)=2\sum_{i=0}^{n-1}T(i)+n^2.

把规模换为 n−1n-1:

(n−1)T(n−1)=2∑i=0n−2T(i)+(n−1)2. (n-1)T(n-1)=2\sum_{i=0}^{n-2}T(i)+(n-1)^2.

两式相减,求和只留下最后一项:

nT(n)−(n−1)T(n−1)=2T(n−1)+2n−1, nT(n)-(n-1)T(n-1)=2T(n-1)+2n-1,

于是:

nT(n)=(n+1)T(n−1)+2n−1. nT(n)=(n+1)T(n-1)+2n-1.

求和项由此消去,递推只剩相邻两个规模。

3. 除以 n(n+1)n(n+1),得到可累加的形式

T(n)n+1=T(n−1)n+2n−1n(n+1)≤T(n−1)n+2n+1. \frac{T(n)}{n+1} =\frac{T(n-1)}n+\frac{2n-1}{n(n+1)} \le\frac{T(n-1)}n+\frac2{n+1}.

令 S(n)=T(n)/(n+1)S(n)=T(n)/(n+1),就有 S(n)≤S(n−1)+2/(n+1)S(n)\le S(n-1)+2/(n+1)。展开至一个固定初值 n0n_0:

T(n)n+1≤T(n0)n0+1+2∑j=n0+1n1j+1=O(logn). \frac{T(n)}{n+1} \le \frac{T(n_0)}{n_0+1} +2\sum_{j=n_0+1}^{n}\frac1{j+1} =O(\log n).

因此:

T(n)=O(nlogn). \boxed{T(n)=O(n\log n)}.

若选择使递推在 n=1n=1 也成立的规范化初值,便可直接写成课件中的 T(1)/2+2(1/3+⋯+1/(n+1))T(1)/2+2(1/3+\cdots+1/(n+1))。若程序在长度为 1 时立即返回,从 n0=2n_0=2 开始展开即可,渐近结论一致。

调和级数产生对数,因为:

∑j=1n1j≤1+∫1ndxx=1+lnn. \sum_{j=1}^{n}\frac1j\le 1+\int_1^n\frac{dx}{x}=1+\ln n.

均衡递归树因为每次规模约减半而产生对数层数。这里则先对所有枢轴秩取平均,再由调和级数得到对数因子,因此允许部分划分很不均衡。

4. 为什么随机版本仍可能很慢

互异元素下,每次恰好选到当前最小值这一种具体序列的概率为:

1n⋅1n−1⋯12=1n!. \frac1n\cdot\frac1{n-1}\cdots\frac12=\frac1{n!}.

这个概率对应一条指定的极端路径。分析算法整体变慢的概率,还要考虑其他坏路径。上面的递推证明了期望为 O(nlogn)O(n\log n);若要得到指数衰减的尾界等更强的高概率结论,还需额外论证,不能由期望上界直接推出。

5. 补充推导:精确比较次数

如果只统计划分时的关键字比较,令 CnC_n 为期望比较次数,C0=C1=0C_0=C_1=0,则:

Cn=n−1+2n∑i=0n−1Ci. C_n=n-1+\frac2n\sum_{i=0}^{n-1}C_i.

设排好序后各元素为 z1<⋯<znz_1<\cdots<z_n。一对 zi,zjz_i,z_j 只有在区间 zi,…,zjz_i,\ldots,z_j 中最先成为枢轴的是某个端点时才会相互比较,因此:

Pr(zi 与 zj 比较)=2j−i+1. \Pr(z_i\text{ 与 }z_j\text{ 比较})=\frac2{j-i+1}.

利用期望的线性性求和:

𝔼[Cn]=∑1≤i<j≤n2j−i+1=2(n+1)Hn−4n,Hn=∑j=1n1j. \mathbb E[C_n] =\sum_{1\le i<j\le n}\frac2{j-i+1} =2(n+1)H_n-4n, \qquad H_n=\sum_{j=1}^{n}\frac1j.

最坏比较次数为 n(n−1)/2n(n-1)/2。下图由这两个公式绘制,比较的是理论计数:

互异元素下,随机快速排序的期望比较次数与最坏比较次数;双对数坐标展示增长速度。

期望比较次数约为 2nlnn2n\ln n,最坏比较次数按二次增长。这里的 CnC_n 只统计关键字比较;前面将每层全部线性工作简写为 nn 的 T(n)T(n),采用的是另一种计量单位。

六、Quickselect:只递归包含目标秩的一侧

若目标是第 kk 小元素,每次划分后只需判断枢轴的最终位置:

def quickselect(a, rank, rng=None):
    if not 0 <= rank < len(a):
        raise ValueError("rank must be a valid zero-based index")
    if rng is None:
        rng = Random()
    p, r = 0, len(a) - 1
    while p <= r:
        q = randomized_partition(a, p, r, rng)
        if q == rank:
            return a[q]
        if rank < q:
            r = q - 1
        else:
            p = q + 1

这里的 rank 是 0-based 排名,例如奇数长度数组的中位数对应 rank = len(a) // 2。算法会改动输入数组。

若每次保留的规模约减半,总扫描代价为 n+n/2+n/4+⋯=O(n)n+n/2+n/4+\cdots=O(n)。随机枢轴下的期望线性时间,可以用归纳法证明。设 S(n)S(n) 为所有目标秩中最大的期望代价。固定任意目标秩,枢轴左边有 ii 个元素时,记下一步实际处理的规模为 mim_i;若恰好找到目标,则记为 0。于是:

0≤mi≤max(i,n−1−i)<n. 0\le m_i\le\max(i,n-1-i)<n.

对于 n≥2n\ge2,

1n∑i=0n−1max(i,n−1−i)≤3n4. \frac1n\sum_{i=0}^{n-1}\max(i,n-1-i)\le\frac{3n}{4}.

用归纳假设 S(m)≤amS(m)\le am 控制所有更小规模,对任何目标秩都有:

𝔼[T]≤cn+an∑i=0n−1mi≤cn+3an4≤an,a≥4c. \mathbb E[T]\le cn+\frac an\sum_{i=0}^{n-1}m_i \le cn+\frac{3an}{4}\le an, \qquad a\ge4c.

同一个常数 aa 对所有目标秩都成立,故 S(n)≤anS(n)\le an,有限初值并入常数。因此,互异元素、均匀随机枢轴下的期望时间为 Θ(n)\Theta(n),最坏仍为 Θ(n2)\Theta(n^2)。

课件第 19 页将找中位数的期望时间写成 O(logn)O(\log n),应改为 O(n)O(n)。初始划分就要扫描线性数量的元素,分析总时间还需累加后续各层的扫描工作。要保证确定性的最坏线性时间,则需采用其他枢轴策略,例如 median-of-medians。

七、堆排序与自底向上建堆

1. 建堆、查看堆顶与取出堆顶

每次扫描剩余数组找最小值,连续取出 nn 次的总代价为 Θ(n2)\Theta(n^2)。最小堆要求父节点不大于子节点,因此全局最小值始终在堆顶。

操作 代价 做了什么
自底向上建堆 O(n)O(n) 从整个输入建立堆序
查看最小值 O(1)O(1) 读取堆顶,不删除
取出最小值 O(logn)O(\log n) 删除堆顶,并恢复堆序

课堂将最小堆视作黑盒:先建堆,再反复弹出最小值。

import heapq


def heap_sort(a):
    heap = list(a)
    heapq.heapify(heap)
    result = []
    while heap:
        result.append(heapq.heappop(heap))
    return result

建堆花费 O(n)O(n),随后 nn 次删除各需至多 O(logn)O(\log n),总时间为 O(nlogn)O(n\log n)。上面的实现复制了输入,并单独保存输出,额外空间为 O(n)O(n)。教材中常见的 原地堆排序 使用最大堆,将最大值交换到数组末尾,辅助空间可降至 O(1)O(1)。空间结论取决于采用哪种实现。

2. 补充推导:建堆的 O(nlogn)O(n\log n) 上界为何可以收紧

逐个插入 nn 个数,时间上界为 O(nlogn)O(n\log n)。heapify 采用自底向上调整:大多数节点靠近叶子,调整距离很短,只有少数上层节点可能下降很多层。

高度为 hh 的节点数量至多为 O(n/2h+1)O(n/2^{h+1}),每个节点的调整代价为 O(h)O(h)。因此:

∑h≥0O(n2h+1)O(h)=O(n)∑h≥0h2h+1=O(n). \sum_{h\ge0}O\left(\frac{n}{2^{h+1}}\right)O(h) =O(n)\sum_{h\ge0}\frac{h}{2^{h+1}} =O(n).

课堂主要使用建堆、取堆顶的接口及其复杂度。上面的求和补充了线性建堆的原因,后面的多路归并也会用到这一结论。

八、计数排序与值域大小

1. 算法与例子

假设输入都是正整数,值域为 1..K1..K。建立计数数组 C[0..K]C[0..K],让 C[x]C[x] 记录 xx 出现的次数,再按 1,2,…,K1,2,\ldots,K 的顺序输出。

对课堂例子 [1,5,3,2,2][1,5,3,2,2]:

值 xx 1 2 3 4 5
次数 C[x]C[x] 1 2 1 0 1

输出为 [1,2,2,3,5][1,2,2,3,5]。

def counting_sort(a):
    if not a:
        return []
    upper = max(a)
    counts = [0] * (upper + 1)
    for x in a:
        counts[x] += 1
    result = []
    for x in range(1, upper + 1):
        result.extend([x] * counts[x])
    return result

这段代码要求输入为正整数;若要支持 0 或负整数,需要调整扫描范围或增加偏移。找最大值、统计频次及输出共需 O(n)O(n),初始化和遍历值域需 O(K)O(K),所以:

时间=O(n+K),辅助空间=O(K). \text{时间}=O(n+K),\qquad \text{辅助空间}=O(K).

若把返回的输出数组也计入额外存储,总空间为 O(n+K)O(n+K)。

这个简化版本只输出整数键值。若每条记录还带有其他字段,稳定排序就要保留完整记录及相同键的原有先后顺序,应采用累计计数与稳定放置等标准写法。重复输出相同整数,并不能完成这种记录排序。

2. 数值大小与二进制编码长度

复杂度式中的 KK 表示数值大小,而计算复杂性中的「多项式时间」以输入编码长度 LL 为参照。

正整数 aia_i 的二进制长度是 ⌊lgai⌋+1\lfloor\lg a_i\rfloor+1。变长编码下,总输入长度还要加上分隔或长度信息;通常可以把主要部分写为:

L≍∑i=1n(⌊lgai⌋+1). L\asymp\sum_{i=1}^{n} \bigl(\lfloor\lg a_i\rfloor+1\bigr).

若统一用足够容纳 1..K1..K 的定长字段,单个字段需要 ⌈lg(K+1)⌉\lceil\lg(K+1)\rceil 位,总长度约为 nlgKn\lg K。

数值可以相对编码长度呈指数增长。例如数组只含一个数 2b2^b,存储它需要 b+1b+1 位;若算法初始化从 1 到 2b2^b 的计数表,单这一步就需要 Θ(2b)\Theta(2^b) 的时间和空间。

因此,O(n+K)O(n+K) 虽然是数值参数的多项式,却未必是二进制输入长度的多项式。这类依赖数值大小的界称为 伪多项式时间。若输入额外满足 K=O(nc)K=O(n^c),其中 cc 为固定常数,则该算法在这一受限输入族上是多项式时间;当 K=O(n)K=O(n) 时,时间进一步降为线性。

3. 桶排序、基数排序与 Sleep Sort 的条件

课堂还提到了桶排序和基数排序,作为课件延伸。桶排序的期望线性时间依赖适当的输入分布和桶内处理条件;输入不是正整数这一点,本身不足以保证桶排序线性完成。基数排序则需计入位数及每一位的排序成本。

Sleep Sort 按数值设置等待时间,再按唤醒顺序输出。分析它时,要把计时、调度、并发资源和值域大小纳入计算模型;只数代码中的显式比较会漏掉这些代价。系统调度也未必能让任意输入都可靠有序。这个例子说明,复杂度结论必须与计算模型一起理解。

九、比较排序下界:为什么至少需要 Ω(nlogn)\Omega(n\log n) 次比较

1. 用决策树表示算法

限制算法只能通过比较获得键之间的顺序信息。对 nn 个互异元素,一次比较只会产生两个可能结果,可表示为二叉树的一个分支。

树根对应第一次比较;向左或向右表示比较结果;后续节点对应由此前结果决定的下一次比较。到达叶子时,算法已经能确定一个正确的输出下标顺序。

一条根到叶子的路径长度,就是该输入执行的比较次数;树高就是最坏输入所需的比较次数。

2. 为什么至少要有 n!n! 个叶子

把输入位置标记为 a1,…,ana_1,\ldots,a_n。当键互异时,它们可能有 n!n! 种严格全序。一个固定的输出下标顺序,例如 (a2,a1,a3)(a_2,a_1,a_3),只能在与它匹配的全序下正确。

正确的比较排序必须覆盖所有这些可能性。两个需要不同输出顺序的全序不能最终共享同一个输出叶子,因此叶子数至少是 n!n!。

这里区分的是元素相对顺序。即使键可以取无限多种数值,只要全序相同,它们仍可以沿同一条比较路径到达同一叶子。

3. 由叶子数推出高度

高度为 hh 的二叉树最多有 2h2^h 个叶子,因此:

2h≥n!,h≥⌈lg(n!)⌉. 2^h\ge n!, \qquad h\ge\lceil\lg(n!)\rceil.

再证明 lg(n!)=Θ(nlgn)\lg(n!)=\Theta(n\lg n)。上界直接用 n!≤nnn!\le n^n:

lg(n!)≤nlgn. \lg(n!)\le n\lg n.

下界取阶乘中最大的至少 n/2n/2 个因子,每个都不小于 n/2n/2:

n!≥(n/2)n/2,lg(n!)≥n2lgn2=Ω(nlgn). n!\ge (n/2)^{n/2}, \qquad \lg(n!)\ge\frac n2\lg\frac n2=\Omega(n\lg n).

由此得到:

任意正确的比较排序,最坏情况需要 Ω(nlogn) 次比较。 \boxed{\text{任意正确的比较排序,最坏情况需要 } \Omega(n\log n)\text{ 次比较。}}

课件第 30 页在阶乘附近标注了 Θ(nn)\Theta(n^n)。这里应使用粗上界 n!≤nnn!\le n^n,并在取对数后得到 lg(n!)=Θ(nlgn)\lg(n!)=\Theta(n\lg n),不能把前一个标记当作阶乘的等价式。

例如 n=3n=3 时有 6 种全序,二叉树至少要有 6 个叶子,最坏路径至少为 ⌈lg6⌉=3\lceil\lg6\rceil=3。一般的叶子计数只给出下界,不保证存在某个算法恰好达到这个整数值。

4. 下界的适用范围

该下界针对最坏情况。带有序性预检查的算法遇到已排序输入时,仍可在线性扫描后返回;某些输入较容易处理,与最坏情况下界一致。

计数排序通过键值直接寻址计数表,利用了比较模型以外的信息,因此其 O(n+K)O(n+K) 时间与比较排序下界相容。特定分布、重复值结构及其他受限输入族,也可能允许更快的算法。

推广到随机算法的期望下界,还需对输入分布取平均。让 n!n! 种全序等概率出现,任何固定的正确比较决策树,平均叶深都至少为 lg(n!)\lg(n!)。再对随机选择取平均,平均比较次数仍为 Ω(nlogn)\Omega(n\log n),因此至少有一个输入的期望比较次数达到这一量级。这里要区分两个量词顺序:固定随机选择后存在坏输入,并不等于存在一个输入对所有随机选择都坏。

一次二元比较至多提供一比特的分支信息,而排序需要区分 n!n! 种顺序。决策树用叶子数与树高的关系,给出了这一信息量直觉的严格证明。

十、常见排序算法的复杂度对照

下表列出常见实现的复杂度,以及平均或期望结论所需的条件。

算法 最坏时间 平均或期望时间 辅助空间与条件
插入排序 Θ(n2)\Theta(n^2) 随机排列下 Θ(n2)\Theta(n^2) O(1)O(1);近乎有序时为 Θ(n+I)\Theta(n+I)
归并排序 Θ(nlogn)\Theta(n\log n) Θ(nlogn)\Theta(n\log n) 常见数组实现为 O(n)O(n)
随机快速排序 Θ(n2)\Theta(n^2) 互异元素下 Θ(nlogn)\Theta(n\log n) 原地划分;常见递归栈期望 O(logn)O(\log n)
原地堆排序 O(nlogn)O(n\log n) O(nlogn)O(n\log n) 上界 O(1)O(1);使用最大堆原地放置
计数排序 Θ(n+K)\Theta(n+K) Θ(n+K)\Theta(n+K) 计数表 O(K)O(K);含输出为 O(n+K)O(n+K)

其中 II 为当前数组的逆序对数:若 i<ji<j 且 A[i]>A[j]A[i]>A[j],两者就构成一个逆序对。插入排序每次向右移动一个前驱元素,都会消除一个逆序对,第三道作业将据此计算移动次数。

十一、作业 1:非递归的线性时间最大子数组

1. 题意与状态分析

来源:课件第 32 页,CLRS 练习 4.1-5。

给定非空数组 AA,元素可以为正、负或零。求一个 非空连续子数组,使元素和最大。要求从左向右扫描,采用非递归算法,在线性时间内完成。

题目提示:已知前缀 A[0..j]A[0..j] 的答案,扩展到 A[0..j+1]A[0..j+1] 后,最优解只有两种位置关系:

  1. 完全位于旧前缀中。
  2. 以新元素 A[j+1]A[j+1] 结尾。

因此需要同时记录整个前缀的最佳值,以及恰好在当前位置结束的最佳值。前者保存已有答案,后者决定新元素接在哪一段后面;只保留全局最大值会缺少后一项信息。

2. 两个状态与递推

定义:

Ej=max0≤i≤j∑t=ijA[t], E_j=\max_{0\le i\le j}\sum_{t=i}^{j}A[t],

即以位置 jj 结尾的最大非空子数组和。另设:

Bj=max0≤i≤t≤j∑u=itA[u], B_j=\max_{0\le i\le t\le j}\sum_{u=i}^{t}A[u],

即整个前缀 A[0..j]A[0..j] 中的最大非空子数组和。

以 jj 结尾的最优区间,要么只选 A[j]A[j],要么把一个以 j−1j-1 结尾的最优区间延长:

Ej=max{A[j],Ej−1+A[j]}. E_j=\max\{A[j],E_{j-1}+A[j]\}.

前缀最佳值则为:

Bj=max{Bj−1,Ej}. B_j=\max\{B_{j-1},E_j\}.

初值为 E0=B0=A[0]E_0=B_0=A[0]。旧后缀贡献为负时,从当前元素重新开始更优。这一选择取决于以当前位置结束的状态,不能由此前的全局最佳值决定。

3. 返回最大和与左右端点的实现

def max_subarray(a):
    if not a:
        raise ValueError("nonempty subarray requires nonempty input")
    end_sum = best_sum = a[0]
    end_left = best_left = best_right = 0

    for j in range(1, len(a)):
        if end_sum + a[j] < a[j]:
            end_sum = a[j]
            end_left = j
        else:
            end_sum += a[j]
        if end_sum > best_sum:
            best_sum = end_sum
            best_left, best_right = end_left, j

    return best_sum, best_left, best_right

返回值为 (最大和, 左端点, 右端点)。相等时保留已有答案,因此有多个最优区间时,会返回最先记录的那个,满足题目求一个最优区间的要求。

4. 手算完整过程

取:

A=[−2,1,−3,4,−1,2,1,−5,4]. A=[-2,1,-3,4,-1,2,1,-5,4].

jj A[j]A[j] EjE_j 当前结尾区间 BjB_j 已记录的最佳区间
0 -2 -2 [0,0][0,0] -2 [0,0][0,0]
1 1 1 [1,1][1,1] 1 [1,1][1,1]
2 -3 -2 [1,2][1,2] 1 [1,1][1,1]
3 4 4 [3,3][3,3] 4 [3,3][3,3]
4 -1 3 [3,4][3,4] 4 [3,3][3,3]
5 2 5 [3,5][3,5] 5 [3,5][3,5]
6 1 6 [3,6][3,6] 6 [3,6][3,6]
7 -5 1 [3,7][3,7] 6 [3,6][3,6]
8 4 5 [3,8][3,8] 6 [3,6][3,6]

答案为 [4,−1,2,1][4,-1,2,1],总和为 6,端点为 [3,6][3,6]。处理到位置 7 时,结尾状态的和下降,但记录的全局最佳区间保持不变。

5. 正确性证明

循环处理完下标 jj 后,保持两个不变式:

  1. end_sum 等于所有以 jj 结尾的非空子数组中的最大和,end_left 是对应起点。
  2. best_sum 等于前缀 A[0..j]A[0..j] 中所有非空子数组的最大和,记录的端点对应一个达到该和的区间。

初始 j=0j=0 时只有一个非空区间 [0,0][0,0],两个状态均取 A[0]A[0],成立。

假设处理完 j−1j-1 时两个不变式成立。以 jj 结尾的非空区间,要么从 jj 开始,要么由以 j−1j-1 结尾的区间延长。后一类都加上同一个新元素,选旧区间中和最大的那个即可,因此第一次更新得到 EjE_j。前缀的最优区间则要么不经过 jj,要么以 jj 结尾,第二次更新据此得到 BjB_j。两次选择都同步维护端点,所以不变式继续成立。

循环结束时 j=n−1j=n-1,前缀就是整个数组,因此返回值正确。

6. 边界与复杂度

数组全为负数时,例如 [−5,−2,−8][-5,-2,-8],答案是单个元素 [−2][-2],返回 (−2,1,1)(-2,1,1)。若把最佳值初始化为 0,便会错误地返回一个不允许的空子数组。

长度为 1 时,直接返回唯一元素。空数组不满足输入要求,代码会抛出异常。若题目改为允许空子数组,可以将答案下限设为 0,但也要相应修改状态定义与证明,和本题的非空约定区分开。

每个元素只更新固定数量的变量,因此时间为 Θ(n)\Theta(n),辅助空间为 O(1)O(1)。上一课的分治方法花费 Θ(nlogn)\Theta(n\log n);这里用一个最佳结尾状态,保存下一次扩展所需的跨边界信息。

十二、作业 2:用最小堆合并 kk 个有序表

1. 题意与关键观察

来源:课件第 33 页,CLRS 练习 6.5-9。

给定 kk 个已经分别按非降序排列的表,总元素数为 nn。将它们合成一个有序表,要求时间 O(nlgk)O(n\lg k)。提示是使用最小堆进行多路归并。

每张有序表中,第一个尚未输出的元素就是剩余部分的最小值。因此,只需比较各非空表的当前表头,就能找到下一个输出值。

堆中保存至多 kk 个候选值。取出一个表头后,只需从它所属的表补入后继。

2. 堆节点保存什么

对于数组形式的输入表,堆节点设为:

(value,list_id,index). (\text{value},\text{list\_id},\text{index}).

第一个字段决定数值大小;后两个字段记录来源,便于找到后继。值相等时,Python 元组继续比较表号和下标,因此可以正常处理重复值,也不需要比较不可排序的自定义节点。

def merge_sorted_lists(lists):
    heap = [
        (row[0], list_id, 0)
        for list_id, row in enumerate(lists)
        if row
    ]
    heapq.heapify(heap)
    result = []
    while heap:
        value, list_id, index = heapq.heappop(heap)
        result.append(value)
        next_index = index + 1
        if next_index < len(lists[list_id]):
            next_value = lists[list_id][next_index]
            heapq.heappush(heap, (next_value, list_id, next_index))
    return result

若输入是链表,则每个堆节点保存当前节点及表号,弹出后沿 next 指针加入后继,算法结构不变。

3. 一次合并的全过程

设:

L0=[1,4,7],L1=[1,3,8],L2=[2,6]. L_0=[1,4,7],\quad L_1=[1,3,8],\quad L_2=[2,6].

初始候选为 (1,0,0),(1,1,0),(2,2,0)(1,0,0),(1,1,0),(2,2,0)。下表为便于阅读,按数值和表号列出候选集合;实际堆数组的排列可能不同:

第几次取出 输出值与来源 加入的后继 取出后尚在堆中的候选值
1 1,来自 L0L_0 4 1(L1),2(L2),4(L0)1(L_1),2(L_2),4(L_0)
2 1,来自 L1L_1 3 2(L2),3(L1),4(L0)2(L_2),3(L_1),4(L_0)
3 2,来自 L2L_2 6 3(L1),4(L0),6(L2)3(L_1),4(L_0),6(L_2)
4 3,来自 L1L_1 8 4(L0),6(L2),8(L1)4(L_0),6(L_2),8(L_1)
5 4,来自 L0L_0 7 6(L2),7(L0),8(L1)6(L_2),7(L_0),8(L_1)
6 6,来自 L2L_2 无 7(L0),8(L1)7(L_0),8(L_1)
7 7,来自 L0L_0 无 8(L1)8(L_1)
8 8,来自 L1L_1 无 空

最终结果是 [1,1,2,3,4,6,7,8][1,1,2,3,4,6,7,8]。每个输入元素进入输出一次;表耗尽后不再向堆中放入候选。

4. 正确性证明

循环开始时保持:

  1. 对每个仍有元素未输出的表,堆中恰有它的第一个未输出元素。
  2. 已输出部分有序,并且不大于任何尚未输出的元素。

初始化把各非空表的第一个元素加入堆,输出为空,成立。

各表内部有序,所以未输出元素都不小于本表的当前表头。堆顶又是所有当前表头中的最小值,也就是全体未输出元素的最小值。将它接在输出末尾,仍保持有序;再加入同一张表的后继,便恢复了每张未耗尽的表恰有一个候选值的不变式。

每轮恰好输出一个元素,循环共进行 nn 轮。堆空时,各表都已经耗尽,所以输出有序并且包含全部输入元素。

5. 时间、空间与特殊情况

若 kk 个表都非空且 k≥2k\ge2,初始化用 O(k)O(k) 时间,heapify 也是 O(k)O(k);共弹出 nn 次,每次至多再插入一次,堆大小始终不超过 kk,因此:

T(n,k)=O(k+nlgk)=O(nlgk), T(n,k)=O(k+n\lg k)=O(n\lg k),

最后一步使用了 k≤nk\le n。堆的辅助空间为 O(k)O(k),若把返回的输出也计入存储,则为 O(n+k)O(n+k)。

如果允许大量空表,扫描这 kk 个输入表头本身就需 O(k)O(k)。设其中非空表数为 k′k',更完整的表达是:

O(k+nlogmax(2,k′)). O\bigl(k+n\log\max(2,k')\bigr).

k=0k=0 时返回空表;只有一个非空表时,复制输出仍需 Θ(n)\Theta(n),即使 log1=0\log1=0,总时间也不为零。题目常用的 O(nlgk)O(n\lg k) 写法默认至少合并两张非空表。

逐个扫描所有当前表头,每输出一个元素需要 O(k)O(k),总计 O(nk)O(nk);最小堆把这一步的维护成本降到了 O(logk)O(\log k)。

十三、作业 3:截断快速排序,再对全数组做插入排序

1. 题意中的执行顺序

来源:课件第 34 页,CLRS 练习 7.4-5。

修改快速排序:调用到一个 少于 kk 个元素 的子数组时,直接返回,让这个小区间暂时无序。整个快速排序阶段结束后,再对 整个数组 执行一次插入排序。

要求证明期望时间为:

O(nk+nlg(n/k)), \boxed{O\bigl(nk+n\lg(n/k)\bigr)},

并讨论理论上、实践中如何选择 kk。

分析采用互异元素和均匀随机枢轴,设 2≤k≤n2\le k\le n。截止条件严格为 m<km<k,长度恰好为 kk 的子数组仍要划分。

2. 完整算法

def hybrid_sort(a, k, rng=None):
    if k < 2:
        raise ValueError("cutoff k must be at least 2")
    if rng is None:
        rng = Random()

    def partial_quicksort(p, r):
        if r - p + 1 < k:
            return
        q = randomized_partition(a, p, r, rng)
        partial_quicksort(p, q - 1)
        partial_quicksort(q + 1, r)

    partial_quicksort(0, len(a) - 1)

    for j in range(1, len(a)):
        key = a[j]
        i = j - 1
        while i >= 0 and a[i] > key:
            a[i + 1] = a[i]
            i -= 1
        a[i + 1] = key
    return a

代码复用前面的 randomized_partition,可接受空数组及 k>nk>n 的情况;后者会直接进入全数组插入排序。题目中含 lg(n/k)\lg(n/k) 的复杂度分析,采用的范围为 2≤k≤n2\le k\le n。

前面的划分只交换元素,最后的插入排序又会排好整个数组,因此算法正确。分析运行时间时,需要先说明第一阶段留下的数组有多接近有序。

3. 未排序小块之间的顺序

递归在小于 kk 的区间上停止。这些终止区间内部可以无序,但它们之间的顺序已经由祖先枢轴确定。

任取两个不同的终止区间,考虑把它们首次分开的祖先划分。左侧全部元素小于该枢轴,右侧全部元素大于该枢轴,所以左区间中的每个元素都小于右区间中的每个元素。已经就位的枢轴也不会与其他区间形成逆序。

因此,剩余逆序对只可能出现在同一个未排序小块内部。

以 k=4k=4 为例,一种合法的第一阶段结果是:

[3,1,2]|4|[6,5]|7|[9,8]. [3,1,2]\;|\;4\;|\;[6,5]\;|\;7\;|\;[9,8].

其中 4 和 7 是已经固定的枢轴,三个小块的长度分别为 3、2、2,均小于 4。小块内部尚未排序,块间已满足前块所有值小于后块所有值的关系。

4. 插入排序的代价用逆序对计量

标准插入排序插入 key 时,每向右移动一个比它大的前驱元素,就消除一个逆序对。每个原始逆序对恰好引起一次这种移动,加上每轮固定开销,运行时间为:

Θ(n+I), \Theta(n+I),

其中 II 是第一阶段结束后的逆序对数。

设未排序小块长度为 m1,m2,…,msm_1,m_2,\ldots,m_s。这些块互不重叠,满足 mi<km_i<k、∑imi≤n\sum_i m_i\le n。长度为 mim_i 的块至多有 (mi2)\binom{m_i}{2} 个逆序对,所以:

I≤∑i=1s(mi2)≤k−12∑i=1smi≤n(k−1)2=O(nk). I\le\sum_{i=1}^{s}\binom{m_i}{2} \le\frac{k-1}{2}\sum_{i=1}^{s}m_i \le\frac{n(k-1)}2 =O(nk).

因此,最后一次 全数组 插入排序需要 O(n+nk)=O(nk)O(n+nk)=O(nk)。全局逆序对数限制了整个扫描过程的移动次数,所以即使不逐块排序,也能得到这个上界。

前面的具体例子中,[3,1,2][3,1,2] 有 2 个逆序对,[6,5][6,5] 和 [9,8][9,8] 各有 1 个,总计 I=4I=4。完整数组的插入过程只需 4 次右移:

插入的键 被右移的元素 局部结果
1 3 [1,3,2][1,3,2]
2 3 [1,2,3][1,2,3]
5 6 [5,6][5,6]
8 9 [8,9][8,9]

其余插入轮次只进行固定数量的检查。最终数组为 [1,2,3,4,5,6,7,8,9][1,2,3,4,5,6,7,8,9]。

5. 截断快速排序的期望代价

若每次恰好均分,递归约有 lg(n/k)\lg(n/k) 层,每层处理 O(n)O(n) 个元素,于是得到 O(nlg(n/k))O(n\lg(n/k))。这是均衡划分下的直观分析。要覆盖随机快速排序中的不均衡划分,还需计算达到截止规模之前的期望工作量。

将长度为 mm 的一次划分所需的 Θ(m)\Theta(m) 工作,平均分摊给区间内的每个元素。固定任意原始元素 xx,跟踪它在尚需划分的子问题中经历的区间规模。

称某次枢轴为「好枢轴」,若它的 1-based 秩 rr 满足:

⌊m/4⌋+1≤r≤⌈3m/4⌉. \lfloor m/4\rfloor+1\le r\le\lceil3m/4\rceil.

这些秩至少占一半,所以每次条件概率至少为 1/21/2。取到好枢轴后,若 xx 本身就是枢轴,它退出递归;否则它进入的那一侧规模至多为 3m/43m/4,取整不会破坏这个上界。

从规模 nn 缩小到小于 kk,至多需要:

g=⌊log4/3nk⌋+1 g=\left\lfloor\log_{4/3}\frac nk\right\rfloor+1

次这样的成功缩小。即使中间出现坏划分,每等到一次好枢轴,期望尝试次数也至多为 2:给定此前任意划分历史,下一次选中好枢轴的条件概率始终至少为 1/21/2。如果元素提前成为枢轴,跟踪还会更早结束。

因此,一个元素参与划分的期望次数为:

O(1+lognk). O\left(1+\log\frac nk\right).

再对 nn 个元素求和,利用期望的线性性:

𝔼[第一阶段代价]=O(n+nlognk). \mathbb E[\text{第一阶段代价}] =O\left(n+n\log\frac nk\right).

不同元素的递归路径可以相互依赖。上述求和只用到每步随机枢轴的条件概率,以及期望的线性性,无须假设路径独立或每层均衡。

6. 合并两阶段的界

加入插入排序以及递归调用的线性级开销:

𝔼[T(n,k)]=O(n+nlgnk+nk)=O(nk+nlgnk). \mathbb E[T(n,k)] =O\left(n+n\lg\frac nk+nk\right) =\boxed{O\left(nk+n\lg\frac nk\right)}.

最后一步利用 k≥2k\ge2,将 O(n)O(n) 吸收到 O(nk)O(nk) 中。特别地,k=nk=n 时虽然 lg(n/k)=0\lg(n/k)=0,第一阶段仍需一次线性划分。这部分由总界中的 nknk 项覆盖,单独计算第一阶段时仍要保留。

这个界是随机枢轴下的期望结论。若连续选到很差的枢轴,第一阶段仍可能花费二次时间。输入含大量重复值、继续采用二路 Lomuto 划分时,互异元素下的期望证明也不适用。

7. 理论上怎样选择 kk

若目标是保持最优的渐近量级,取一个固定常数 kk 即可:

nk=O(n),nlg(n/k)=Θ(nlogn). nk=O(n),\qquad n\lg(n/k)=\Theta(n\log n).

取 k=O(logn)k=O(\log n),总界也保持在 O(nlogn)O(n\log n),与固定常数的渐近阶相同;取 k=nk=n 时,上界则为 O(n2)O(n^2)。

若进一步比较两阶段的成本常数,可以使用模型:

F(k)=anln(n/k)+bnk,a,b>0. F(k)=a\,n\ln(n/k)+b\,nk,\qquad a,b>0.

把 kk 暂当作连续变量,则:

F′(k)=−ank+bn=0⇒k=ab. F'(k)=-\frac{an}{k}+bn=0 \quad\Longrightarrow\quad k=\frac ab.

这个模型给出的理想阈值为常数规模,具体取决于两阶段的成本系数。它不能确定一个适用于所有机器和程序的整数;渐近大 OO 隐藏了这些系数,实际最优阈值仍需测量。

8. 实践中怎样选择 kk

固定实现与硬件,在同一批数据上比较几个小阈值。测试应覆盖随机、近乎有序、逆序及重复值较多的输入,并通过重复运行观察稳定耗时,减少随机枢轴波动对判断的干扰。

短数组上,插入排序的循环紧凑,局部访问连续;快速排序则要承担枢轴选择、划分和递归管理的开销。阈值决定何时切换两种算法,合适的取值还受元素大小、比较函数成本和缓存行为影响,需要通过测量确定。

9. 证明中需要保留的条件

十四、复习题

  1. 多数元素的 count 为什么不是实际出现次数?去掉存在性保证后应补哪一步?
  2. Lomuto 划分的四个区域是什么?为什么最后交换后还不能说左右两侧已经有序?
  3. 为什么互异元素下,枢轴秩的均匀分布足以分析任意固定输入?
  4. 快速排序的期望递推为什么能通过相邻规模作差消掉求和?
  5. 递归层数为对数,为什么 Quickselect 的时间仍为线性?
  6. 自底向上建堆为什么是线性时间?查看堆顶与取出堆顶的成本有何区别?
  7. O(n+K)O(n+K) 为什么未必是关于二进制编码长度的多项式?
  8. 比较排序的叶子为什么至少有 n!n! 个?下界为什么允许某些输入在线性时间内完成?
  9. 最大子数组的两个状态各自覆盖哪些候选区间?
  10. 多路归并为什么只需为每张表保留一个候选元素?
  11. 混合排序第一阶段之后,为什么逆序对只能留在小块内部?
  12. 怎样在允许随机坏划分的情况下,证明第一阶段的期望代价?

附 · 资料下载

主要依据为课程课件《04-advanced_sorting》、本次课堂转写《算法课排序复杂度与决策树证明》,以及当天课堂摘要。三道作业的编号、输入要求和目标复杂度均以课件末尾题目为准。

单页手写提纲用于快速回顾课堂主线,详细推导和作业解答见本文:

Day4 排序进阶单页手写提纲,概览随机快速排序、堆排序、计数排序和比较下界。