Chapter 3 · Characterizing Running Times

从“哪条曲线最终会赢”开始

先预测：算法A耗时$1000n$，算法B耗时$n^2$。在小输入上B可能更快，但随着$n$增长，二次项最终超过任何固定倍数的线性项。Characterizing Running Times要刻画的正是这种“越过某个阈值以后”的关系，而不是一台机器上的一次计时。

渐近分析保留增长率，隐藏固定机器速度、实现常数和低阶项。它不宣称常数不重要，而是把问题拆成两层：先证明规模怎样增长，再用测量选择同一增长等级中的实现。

3.1 O-notation, Ω-notation, and Θ-notation

上界、下界与紧确界

设$f$和$g$在自然数输入上最终非负。给出最终上界；给出最终下界；同时给出两边。

形式上，存在正常数$c,c_1,c_2$和阈值$n_0$，使所有$n\ge n_0$满足相应不等式：

例如$f(n)=3n^2+2n+1$。对$n\ge1$，有$f(n)\le6n^2$且$f(n)\ge3n^2$，所以$f\in\Theta(n^2)$。常数并不唯一；证明只需给出一组有效见证。

“紧确”不等于“精确公式”

允许常数倍误差。$4n^2+3n$与$n^2$的比值趋近4，但写$\Theta(n^2)$并不保留系数4。若需求是预测实际延迟，就必须保留操作成本、缓存行为与测量误差，不能只交一条Θ结论。

$f\in\Theta(g)$一定推出$f\in O(g)$和$f\in\Omega(g)$。反向只有两边同时成立才成立：

一个函数可以拥有松上界。例如$n\in O(n^2)$为真，却不紧确；通常应报告可证明的最紧常用界$n\in\Theta(n)$，让读者看见真实增长等级。

输入情形与记号方向不是同一件事

“最坏情况”先在长度$n$的实例集合上取最大运行时间，得到函数$T_{\mathrm{worst}}(n)$；随后才能说它属于$O(g)$、$\Omega(g)$或$\Theta(g)$。平均情况与最好情况也各自产生自己的函数，它们同样可以拥有上界和下界。

3.2 Asymptotic notation: formal definitions

集合与量词

严格说，$O(g)$是函数集合，正确写法是$f\in O(g)$。算法文献常写$f=O(g)$，这里等号是一种约定：右侧代表集合中的某个未命名函数。它不能像普通等式那样随意反向推理。例如由$f=O(g)$不能推出$g=O(f)$。

定义最关键的是量词顺序。对于O记号：

常数$c$和$n_0$必须在“对所有后续$n$”之前固定。若允许每个$n$选择$c(n)=f(n)/g(n)$，几乎所有正函数都能通过，定义便失去区分增长率的能力。

有限测试只能找反例，不能证明全称命题。程序可以帮助猜测见证，但最终证明要把所有$n\ge n_0$纳入代数推导。对于$3n^2+2n+1$，利用$n\le n^2$和$1\le n^2$即可一次覆盖全部$n\ge1$。

function sampledUpperBound(
  f: (n: number) => number,
  g: (n: number) => number,
  c: number,
  n0: number,
) {
  for (let n = n0; n <= 10_000; n += 1) {
    if (f(n) > c * g(n)) return { ok: false, counterexample: n };
  }
  return { ok: true, counterexample: null }; // evidence, not a proof
}

严格上界与严格下界

小写$o$排除同阶常数倍：$f\in o(g)$表示对每个$c>0$都存在阈值，使$f(n)<cg(n)$；小写$\omega$反向表示$f$严格快于$g$。当极限存在且$g$最终为正时，可以用比值理解：

例如$n\lg n\in o(n^2)$，而$2^n\in\omega(n^k)$对任意固定$k$成立。注意比值法是方便工具，不替代定义；极限不存在时，仍应回到最终不等式和上下极限。

渐近关系的代数性质

Θ关系具有自反、对称和传递性，像函数增长等级上的等价关系。O与Ω各自传递，并满足转置对称：$f\in O(g)$当且仅当$g\in\Omega(f)$。这些性质允许把多步界串联，但每步都要保证函数最终非负。

和式通常由较快增长项支配。若$f_1,f_2$最终非负，则：

乘积则相乘各自的界。若项会正负抵消，上述直觉可能失效，因此运行时间分析通常先把成本建模为非负函数。

3.3 Standard notations and common functions

单调性、取整与模运算

算法规模是整数，因此分治常出现$\lfloor n/2\rfloor$和$\lceil n/2\rceil$。取整只造成不足1的误差，通常不改变渐近等级，但在递推基例、数组边界和精确证明中不能直接删除。恒等式$\lfloor x\rfloor\le x\le\lceil x\rceil$提供上下夹界。

模运算把整数映射到固定余数集合，$a\bmod n\in\{0,\ldots,n-1\}$，用于环形缓冲区、哈希桶和周期状态。对负数时，不同语言的余数约定可能不同；数学证明与代码必须采用同一语义。

多项式、指数与对数

次数为$d$且首项系数为正的多项式$p(n)$满足$p(n)\in\Theta(n^d)$。任意固定多项式最终都慢于底数大于1的指数函数，而不同底数的指数函数不只差常数倍。

对数把乘法规模变成加法层数。换底公式表明固定底数只贡献常数：

因此算法分析常把$\lg n$写作二进制对数，而在Θ记号中省略底数。常用恒等式包括$\lg(ab)=\lg a+\lg b$、$\lg(a^k)=k\lg a$以及$a^{\lg_b n}=n^{\lg_b a}$。最后一个等式经常用于把递归树的分支数改写为$n$的幂。

阶乘、函数迭代与Fibonacci

阶乘计算排列数量，增长快于任意固定指数$c^n$但慢于$n^n$。Stirling近似给出可用于取对数的紧确表达：

函数迭代$f^{(i)}(n)$表示把$f$连续应用$i$次，不是幂。$\lg^*n$就是达到常数范围所需的迭代次数，在并查集和某些高级算法中出现。即使$n$巨大，$\lg^*n$仍很小，但它不是常数函数。

Fibonacci数满足$F_i=F_{i-1}+F_{i-2}$。特征根公式显示$F_i$按黄金比例$\varphi^i$指数增长，因此Fibonacci堆或递归算法中的“阶数为对数”结论，往往来自节点规模至少按Fibonacci数增长。

growth ladder for fixed k and c > 1:
1 ≺ lg* n ≺ lg lg n ≺ lg n ≺ n^k ≺ c^n ≺ n! ≺ n^n

这条阶梯要求参数固定。若$k$或$c$随$n$变化，比较关系必须重新证明；“指数一定比多项式快”隐含指数底数固定大于1、多项式次数固定。

小结

Chapter 3 Characterizing Running Times把“增长得更快”变成可证明命题。O记号给最终上界，Ω记号给最终下界，Θ记号要求两边同时成立；o与ω表达严格的低阶和高阶关系。它们都是函数集合，定义依赖固定正常数、阈值和覆盖无限后缀的量词顺序。

标准记号与常用函数提供化简词汇：取整处理离散规模，模运算处理周期，多项式由最高次数支配，固定底对数只差常数，指数最终超过固定次数多项式，Stirling公式刻画阶乘，迭代对数和Fibonacci则连接后续数据结构分析。一个完整结果必须同时说明分析对象、界的方向、见证与使用的函数恒等式。