第4卷第6章难以捉摸的未来

从顺序查找的精确步数进入O、Ω、Θ渐近记号，逐行证明二分查找为O(log n)、冒泡排序为O(n²)，再用比较树建立所有比较排序的Ω(n log n)下界。

学习目标

能用常数、阈值和量词定义判断 O(f(n))、Ω(f(n)) 与 Θ(f(n))，并区分上界、下界和紧确阶
能逐行追踪二分查找与冒泡排序，分别从候选区间减半和三角和推导 O(log n)、O(n²)
能把比较排序抽象成比较树，用 2^h≥n! 与阶乘下界证明所有比较排序的 Ω(n log n) 下界
能用交互实验比较常数优化、增长阶与信息下界，判断预排序成本何时值得付出

从两条直线开始：快一点与改变增长阶不是一回事

章首《鲁滨逊漂流记》把木匠工具箱称为比一船黄金更贵重的厚礼。本章的“工具箱”是渐近记号、逐行计数、对数和比较树。它们不预测未来每一步，却能在输入巨大时约束算法会增长到什么程度。

先预测：

3n+7始终比4n+5增长得慢一些，为什么两者仍同为O(n)？
n=16的有序数组，二分查找最坏要比较几次？
冒泡排序把大数像气泡一样送到右端，嵌套循环为什么形成二次阶？
不看任何具体排序代码，怎样证明所有比较排序都不可能突破n log n下界？

6.1 约定的记忆

“明明你说了明天继续的。”米尔嘉在河畔重复。她说的是医院里的哥哥：明明约定明天再见、继续研究数学，却再也没能兑现。晚霞、两只乌鸦、远处电车和空无一人的河岸围住了这段记忆。

“我”没有追问她把谁当成了自己，只让她靠在肩上。她想的不是眼前的人，而是反复想起已经去世的哥哥。“我”不知道什么才是正确答案，只确认现在应该留在她身边。她起身后抓住“我”的手狠狠咬下，说自己明明想一直留在他身边。上一章误喊“哥哥”的瞬间，在这里展开成无法履行的约定。

6.2 阶

6.2.1 更快的算法

黄金周里，应考生仍在学校图书室做模拟题。泰朵拉与理沙继续研究算法速度，从第2章的最坏情况步数出发：

T_L(n)=4n+5, \qquad T_S(n)=3n+7.

这里L表示普通顺序查找，S表示带哨兵顺序查找，n是数列大小。两式相减：

T_L(n)-T_S(n)=n-2.

所以当n大于2时：

T_L(n)>T_S(n).

精确计数说明哨兵版最大运行步数更少，图像上3n+7最终位于4n+5下方。泰朵拉却追问：既然已有可靠不等式，还能带来什么？

6.2.2 至多为n阶

米尔嘉回答：“分析未必都要朝更精确的方向发展。”若存在常数N与正数C，使所有n≥N都满足：

|T(n)|\le Cn,

就写作：

T(n)=O(n).

给出最终上界。T(n)=O(n)读作，不是说T(n)被某个固定常数限制，也不是说它不会趋向无穷。

在线性上界的特例中，约束可压写为|T(n)|≤Cn。

6.2.3 出题

回到定义就能完成米尔嘉的题：

4n+5=O(n)：可取N=5、C=5，此后4n+5≤5n。
n+1000=O(n)：可取N=1000、C=2，此后n+1000≤2n。
n²=O(n)不成立：任给常数C，取n>C便有n²>Cn。

大O在做。n、n+1000、4n+5在“至多为线性阶”这一尺度下同类。哨兵虽然减少约四分之一的主导步数，却没有把顺序查找从O(n)改造成更低阶算法。

6.2.4 至多为f(n)阶

一般定义是：

T(n)=O(f(n)) \Longleftrightarrow \exists N\ \exists C>0\ \forall n\ge N: |T(n)|\le C f(n).

例如：

2n^3+3n^2+4n+5=O(n^3).

线性排版就是2n³+3n²+4n+5=O(n³)。

因为大O只给上界，n=O(n²)甚至4n+5=O(n^{1000})都正确，只是丢掉了可用信息。把O(f(n))误读成“恰好为f(n)阶”会造成混乱。

表达下界；表达紧确阶：

T(n)=\Theta(f(n)) \Longleftrightarrow T(n)=O(f(n)) \quad\text{且}\quad T(n)=\Omega(f(n)).

T(n)=O(1)表示函数存在常数上界，不表示它一定是常数函数，也不保证极限存在；例如(-1)^n始终有界却来回波动。

6.2.5 log n

增长阶不只整数次幂。常见层级是：

O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^2) \subset O(2^n).

O(log n)小于线性阶，O(n log n)则位于线性与二次之间。渐近记号中的对数通常省略底，因为换底公式只引入常数倍：

\log_a n=\frac{\log_b n}{\log_b a}.

先给证据不等式，再决定是上界、下界还是紧确阶。

6.3 查找

6.3.1 二分查找

泰朵拉问是否真有O(log n)查找。答案是，但它有一个不能漏掉的约定：

A[1]\le A[2]\le\cdots\le A[n].

输入必须已按升序排列。维护候选区间[a,b]：

BINARY-SEARCH(A, n, v)
  a ← 1
  b ← n
  while a ≤ b
    k ← floor((a+b)/2)
    if A[k] = v return FOUND
    else if A[k] < v then a ← k+1
    else b ← k-1
  return NOT-FOUND

保证中点下标为整数，例如floor(2.5)=2、floor(-2.5)=-3。

6.3.2 实例

原章测试用例是：

A=\{26,31,41,53,77,89,93,97\}, \quad n=8, \quad v=77.

逐行调试：

比较	区间 `[a,b]`	中点 `k`	`A[k]`	决策
1	`[1,8]`	4	53	53小于77，令`a=5`
2	`[5,8]`	6	89	89大于77，令`b=5`
3	`[5,5]`	5	77	找到

有序性让A[k]左边或右边的一整段可以安全排除。每比较一次，候选规模约减半；增加一次比较，就能处理约两倍大的数组。

用一句话复述轨迹：区间[1,8]的中点k=4，区间[5,8]的中点k=6，区间[5,5]的中点k=5。

有序性让每次比较都能整段排除候选区间。

6.3.3 分析

理沙逐行统计后，把总运行步数归纳为：

7M+2S+6,

其中M是关键比较次数，S是“找到时为1，否则为0”的指示器。常数和有界指示器不会支配增长，所以只需研究最大比较次数M(n)。

为了构造最坏测试，查找比数组所有元素都大的值，让流程持续走向右半段。小规模表得到：

M(1),M(2),\ldots = 1,2,2,3,3,3,3,4,\ldots

规律可写为：

2^{M(n)-1}\le n.

它的线性写法是2^(M(n)-1)≤n。

两边取以2为底的对数：

M(n)\le1+\log_2 n.

原章再按n的奇偶做数学归纳，证明每次一次比较后进入的右半区规模都足以应用归纳假设。因此：

M(n)=O(\log n),

总运行步数也是：

7M(n)+2S+6=O(\log n).

因此总运行步数也是O(log n)。

6.3.4 前往排序

窗外太阳雨后出现彩虹。泰朵拉说彩虹是《诺亚方舟》中“约定的印记”，让“我”再次想起米尔嘉那句“明明约好了明天再见”。

泰朵拉兴奋地说，只要先排序，就能用二分查找。米尔嘉指出排序本身也要花时间：一次查询可能得不偿失；若要对同一数据进行多次查询，预排序成本才可被后续查询摊薄。于是问题从查找转向排序。

6.4 排序

6.4.1 冒泡排序

的输出要求是：

A[1]\le A[2]\le\cdots\le A[n].

BUBBLE-SORT(A, n)
  m ← n
  while m > 1
    k ← 1
    while k < m
      if A[k] > A[k+1]
        swap A[k], A[k+1]
      k ← k+1
    m ← m-1
  return A

每一趟中，大元素像气泡上浮到右端，所以下一趟不必再访问已经就位的末尾，也就是m每趟减1。

6.4.2 实例

测试输入：

A=\{53,89,41,31,26\}.

第一趟把89逐次交换到最右；后续各趟让53、41、31依次就位，最终得到：

\{26,31,41,53,89\}.

逐行调试不只是展示答案，还要看m如何从5减到2、内层k的扫描长度逐趟缩短。

6.4.3 分析

泰朵拉做到“这里是我不明白的第一线”。她先用“进入次数等于离开次数”分析控制流，理沙把这种流量守恒联想到。

内层条件检查次数形成：

B=n+(n-1)+\cdots+3+2.

这是三角和：

B=\frac{n(n+1)}2-1.

原和可线性写成B=n+(n-1)+...+3+2。

把各行最大运行次数相加，原章归纳成3n²+2n量级；因此：

T_{\text{bubble}}(n)=O(n^2).

也就是冒泡排序最大运行步数为O(n²)。

每趟把一个最大元素送到右端，内层扫描因此形成三角和。

6.4.4 大O表示法的层级

若4n+5=O(n)且3n+7=O(n)，不能推出4n+5=3n+7。原因是O(f(n))表示函数集合，也就是：

O(f) = \left\{ g\ \middle|\ \exists N\ \exists C>0\ \forall n\ge N,\ |g(n)|\le Cf(n) \right\}.

所以T(n)=O(f(n))更接近T∈O(f)，等号不能左右交换。集合包含关系形成层级。大O无视系数和低次项，可能与实测速度不同，却能把算法在巨大输入下的渐近状态传递给别人。

6.5 动态视角、静态视角

6.5.1 需要比较多少次呢

逐行调试必须沿时间和顺序前进，属于；数学公式或一张完整结构图能同时看见全局，属于。米尔嘉提出把动态算法转换成静态构造。

问题是：对n个互不相同元素，任意只靠两两比较的排序算法，最坏比较次数是否至少是n log n阶？研究某一个冒泡程序不能回答“任意算法”的下界。

6.5.2 比较树

每次比较只有两种结果。把所有可能执行路线展开成：

根到叶的一条路径对应某个输入上的比较过程；
内部结点数对应比较次数；-h对应最大比较次数；
为正确排序所有输入，叶子必须覆盖全部n!种排列。

高度为h的二叉树至多有2^h个叶子，因此必须：

2^h\ge n!.

下界来自信息量：每个输入排列都需要一个可区分的叶子。

取对数：

h\ge\log_2(n!).

三元素时需要覆盖3!=6个排列，而高度2至多4叶，所以最坏至少3次比较。

6.5.3 log n! 的评估

不必背斯特林公式也能给出足够的下界。当n≥4时，n!后半段至少有n/2个因子，每个都不小于n/2：

n! \ge \left(\frac n2\right)^{n/2}.

这个阶乘下界可线性写成n!≥(n/2)^(n/2)。

因此：

\begin{aligned} \log_2(n!) &\ge \frac n2\log_2\frac n2\\ &= \frac n2(\log_2n-1)\\ &\ge \frac n4\log_2n. \end{aligned}

所以：

\log(n!)=\Omega(n\log n),

也就是log(n!)=Ω(n log n)。

结合h≥log₂(n!)：

T_{\max}(n)=\Omega(n\log n).

线性写法为T_max(n)=Ω(n log n)。

这不是某个排序算法慢，而是所有比较排序共同的下界。类似比较树还能证明有序数组的比较查找需要Ω(log n)；二分查找已有O(log n)上界，于是它达到：

\Theta(\log n).

因此二分查找达到Θ(log n)。

6.6 传递和学习

6.6.1 传递

泰朵拉意识到：把工作交给计算机，要把想法变成程序；把数学交给后来者，要把想法变成可读的信息。她曾从书和公式的作者那里接收信息，也希望有一天成为，把内容送到自己已经不在的遥远未来。

米尔嘉说论文的本质不是“难”，而是正确记录值得传递的事情；研究是在前人发现上累积自己的新发现；学问是在过去之上筑就现在并展望未来。“站在巨人的肩上”，既是学习，也是传递。

6.6.2 学习

米尔嘉说自己通过书、论文、老师，以及理沙母亲双仓博士在双仓图书馆举办的研讨会学习。理沙突然说“我什么都没学到”，认为母亲什么也没教会自己。

米尔嘉尖锐地指出，机会就在附近，是否参加、是否提问也是学习者的选择。理沙说自己不善表达、不能正常发声，总抓不住机会，现在已经来不及，只能一个人做。米尔嘉则指责她在守护心中的围城。泰朵拉用“欧拉老师的弟子”和斐波那契手势试图调停，却没有让两人和解。

章末高德纳的引语重新钉住工具的读法：O(f(n))是至多为f(n)阶，Ω(f(n))是至少为f(n)阶，Θ(f(n))是恰好为f(n)阶。算法的未来难以逐步捉摸，但增长边界可以被准确传递。

官方概念回收：把边界变成可检查的证据

官方概念锚点补全：当 n大于2 时，3n+7最终位于4n+5下方，这只是常数优化；渐近分析关心存在常数N 和正数C，使某个常数倍从上方限制函数。n²=O(n)不成立，因为任给常数C，取n>C 就会得到 n²>Cn。这是一种函数分类：忽略系数与低次项，不能因此说没有把顺序查找从O(n)改造成更低阶算法。

量词定义会把“大 O”变成证据；4n+5=O(n的1000次方)虽正确却很松。大Ω表示法给下界，大Θ表示法表示上下夹住的紧确阶。对数阶 O(log n) 的含义是输入翻倍只增加常数工作量。二分查找通过比较中点、舍弃一半候选区间实现这一点；向下取整是不超过实数x的最大整数，示例轨迹经过区间[1,8]的中点k=4、区间[5,8]的中点k=6、区间[5,5]的中点k=5。按n的奇偶做数学归纳可得 M(n)=O(log n)，所以总运行步数也是O(log n)。

冒泡排序操作相邻元素，交换逆序对，每一趟把大元素推向右端，m每趟减1；分析中要记录 m如何从5减到2，控制流的进入次数等于离开次数，这与基尔霍夫定律的流量守恒类比，三角和为 n(n+1)/2-1，最终得到 T_bubble(n)=O(n²)。不能推出4n+5=3n+7，因为 O(f(n))表示函数集合，不是普通等式。比较树面对 n个互不相同元素的比较排序，任意算法至少是n log n阶；n!种排列需要由高度为h的二叉树覆盖，树至多有2^h个叶子。阶乘的 n!后半段至少包含 n/2个因子，每个都不小于n/2，取对数可得到 n/2(log₂n-1) 与 n/4 log₂n 的下界。比较查找需要Ω(log n)，二分查找达到Θ(log n)。最后，论文把正确的增长边界交给未来的信息的发送者；“至少为f(n)阶”和“恰好为f(n)阶”分别由 Ω 与 Θ 表达。

分步1 / 4

1. 上界：用常数包住增长

从具体不等式出发，选择阈值 N 和常数 C，把 4n+5 证明为 O(n)，再说明同一函数也可能属于更松的上界。