第 03 章 函数的增长与渐近记号

本章对应原书第 3 章。第 01 章用"去掉低阶项和常系数"得到了 \(\Theta(n^2)\)、\(\Theta(n\lg n)\)，但没有说清 \(\Theta\) 究竟是什么。本章给出五种渐近记号的精确定义，讲清它们在等式里的含义和常见误用，再整理全书反复使用的标准函数：取整、模运算、多项式、指数、对数、阶乘、迭代对数和斐波那契数。这些工具是读懂后面所有复杂度结论的语言，也是评估量化系统能否扩展到更大股票池、更高频数据的基本功。

学习目标

1. 写出 \(\Theta\)、\(O\)、\(\Omega\)、\(o\)、\(\omega\) 的定义，并能用定义（找常数 \(c\)、\(n_0\)）证明或否定一个渐近关系。
2. 分清"最坏运行时间是 \(\Theta(n^2)\)"、"运行时间是 \(O(n^2)\)"、"运行时间是 \(\Omega(n)\)"三种说法的含义。
3. 正确理解公式中的渐近记号代表"匿名函数"，会解读 \(T(n)=2T(n/2)+\Theta(n)\) 这类写法。
4. 熟记增长量级阶梯 \(1\ll\lg^*n\ll\lg\lg n\ll\lg n\ll n^\epsilon\ll n\ll n\lg n\ll n^2\ll c^n\ll n!\ll n^n\)，并能用对数恒等式与 Stirling 公式比较函数。
5. 能用增长率给量化系统的各环节估算成本，并用实测的 log-log 斜率验证；能把滚动窗口统计从 \(\Theta(nw)\) 改写为 \(\Theta(n)\) 的增量算法。

读前导读

这一章在解决什么问题

第 01 章一直在说"插入排序是 \(\Theta(n^2)\)""归并排序是 \(\Theta(n\lg n)\)"，这一章把这些记号说清楚。先抓住最朴素的问法：数据量翻倍时，耗时翻几倍？

• 耗时不变：记作 \(\Theta(1)\)，比如按下标取一个数组元素。
• 耗时只多一点点（加一个常数）：\(\Theta(\lg n)\)，比如在有序数组里二分查找，数据翻倍只多查一次。
• 耗时翻 2 倍：\(\Theta(n)\)，比如把每只股票的收益加总。
• 耗时略多于 2 倍：\(\Theta(n\lg n)\)，比如归并排序。
• 耗时翻 4 倍：\(\Theta(n^2)\)，比如计算所有股票两两之间的相关系数。
• 耗时翻 8 倍：\(\Theta(n^3)\)，比如对 \(n\times n\) 协方差矩阵求逆。
• 数据只多 1 个，耗时就翻倍：\(\Theta(2^n)\)，比如穷举 \(n\) 只资产的所有组合。

渐近记号就是把这种"翻倍规律"写成严格的数学语言。它故意忽略两类东西：常数倍（机器快慢、代码写得好坏）和低阶项（规模小时才显眼的杂项）。这和财务分析里看"增长率"而不是看"某年绝对金额"是同一种思路：比较两家公司的长期前景，看的是收入按什么速度增长，而不是今年谁多赚了几百万。

五个记号可以先这样记：\(O\) 像"不超过"（上限），\(\Omega\) 像"至少"（下限），\(\Theta\) 像"差不多等于"（上下都夹住），\(o\) 和 \(\omega\) 是"严格小于""严格大于"的版本。

需要先想起来的数学

• 量词 \(\exists\) 与 \(\forall\)。 \(\exists\) 读作"存在"，\(\forall\) 读作"对所有"。"\(\exists c>0,\forall n\ge n_0\)：\(f(n)\le cg(n)\)"读作：能找到某个常数 \(c\)，使得从某个 \(n_0\) 往后，每一个 \(n\) 都满足 \(f(n)\le cg(n)\)。顺序很重要：先选 \(c\) 再验证所有 \(n\)，和"对每个 \(n\) 各选一个 \(c\)"完全不同。详见 第 00 册第 08 章 读懂数学证明与符号。
• 集合记号。 \(\{f(n):\ \text{条件}\}\) 表示"所有满足条件的函数组成的集合"，\(\in\) 读作"属于"，\(\subseteq\) 读作"是……的子集"。
• 极限 \(\lim_{n\to\infty}\)。 "\(n\) 越来越大时，这个式子越来越接近什么"。例：\(\lim_{n\to\infty}\frac{2n}{n^2}=\lim\frac{2}{n}=0\)，说明 \(n\) 大了以后 \(2n\) 相对 \(n^2\) 可以忽略。详见 第 00 册第 01 章 函数极限与连续。
• 指数与对数的运算规则。 \(\log(ab)=\log a+\log b\)，\(\log a^n=n\log a\)，换底公式 \(\log_ba=\frac{\log_ca}{\log_cb}\)。例：\(\lg 1000=\frac{\ln 1000}{\ln 2}\approx\frac{6.91}{0.693}\approx9.97\)。你在算连续复利和对数收益时都用过。详见 第 00 册第 04 章 级数与收敛。
• 大 O 的概率版。 读统计文献时见过的 \(O_p(1/\sqrt n)\) 是同一家族的记号。详见 第 00 册第 07 章 概率中的分析工具。

怎么读这一章

3.2 节是核心：\(\Theta\)、\(O\)、\(\Omega\) 的定义、例 1 的证明方法、"运行时间是 \(O(n^2)\)"的确切含义，以及"等式中的渐近记号"四条规则，务必读懂。\(o\)、\(\omega\) 记住"比值趋于 0 或无穷"即可。3.3 节是工具箱，第一次读只需记住三个结论：指数快过任何多项式，多项式快过任何对数的幂，\(\lg(n!)=\Theta(n\lg n)\)；取整恒等式、迭代对数、斐波那契数可以等后面用到时再回查。3.4 节的真假表很适合自测。量化实战部分的"复杂度估算表"非常实用，建议结合自己的研究流程读。

3.1 为什么只看渐近效率

输入规模足够大时，精确运行时间里的常数因子和低阶项被规模本身的影响所淹没。研究规模趋于无穷时运行时间如何增长，叫研究算法的渐近效率（asymptotic efficiency）。除了很小的输入，渐近更有效的算法通常是最好的选择。

渐近记号定义在自然数集 \(\mathbb N=\{0,1,2,\dots\}\) 上的函数，因为运行时间 \(T(n)\) 只在整数规模上有定义。有时会"滥用"到实数域，但要清楚精确含义。渐近记号作用于函数本身，可以描述运行时间、空间，也可以描述与算法无关的函数。使用时要说清指的是哪种运行时间：最坏情况，还是"对所有输入都成立"的总体陈述。

3.2 五种渐近记号

\(\Theta\)：渐近紧确界

对足够大的 \(n\)，\(f(n)\) 被"夹"在 \(c_1g(n)\) 与 \(c_2g(n)\) 之间，称 \(g(n)\) 是 \(f(n)\) 的渐近紧确界（asymptotically tight bound）。\(\Theta(g(n))\) 是一个函数集合，严格应写 \(f(n)\in\Theta(g(n))\)，但习惯写 \(f(n)=\Theta(g(n))\)，这种写法的好处稍后会看到。定义要求成员渐近非负（足够大的 \(n\) 时非负），所以 \(g(n)\) 本身也必须渐近非负，否则集合为空。本章所有记号都默认函数渐近非负。

白话解释：把定义逐字翻译成中文："\(f\) 属于 \(\Theta(g)\)"意思是，能找到两个固定的正数 \(c_1\)、\(c_2\) 和一个起点 \(n_0\)，从 \(n_0\) 往后，\(f(n)\) 永远落在 \(c_1g(n)\) 与 \(c_2g(n)\) 之间。画在图上，\(c_1g\) 和 \(c_2g\) 是两条"护栏"，\(f\) 在 \(n_0\) 之后一直在护栏中间走。 用"翻倍"的语言说：如果 \(f\) 被 \(g\) 的两个常数倍夹住，那么 \(n\) 翻倍时，\(f\) 增长的倍数和 \(g\) 增长的倍数最多差一个固定比例，二者"同速增长"。\(n_0\) 的作用是允许开头一段不守规矩：小规模时杂项可能很显眼，我们不在乎。 金融上的类比：说某基金"跟踪误差有界"，是说它的净值始终在指数的某个上下比例带内，不要求每天都相等。

例 1：证明 \(\frac12n^2-3n=\Theta(n^2)\)。 需要 \(c_1n^2\le\frac12n^2-3n\le c_2n^2\)，两边除以 \(n^2\)：

取 \(c_2=\frac12\)，右边对 \(n\ge1\) 成立；取 \(c_1=\frac1{14}\)，左边对 \(n\ge7\) 成立（\(n=7\) 时 \(\frac12-\frac37=\frac1{14}\)）。所以 \(c_1=\frac1{14}\)、\(c_2=\frac12\)、\(n_0=7\) 即可。常数的选法不唯一。

推导拆解：这类证明的套路是"除掉 \(g(n)\)，看剩下的比值往哪走"。 第一步，两边除以 \(n^2\)（\(n>0\)，不等号方向不变），问题变成：比值 \(r(n)=\frac12-\frac3n\) 能否被两个正常数夹住。 第二步，看 \(r(n)\) 的走势：\(\frac3n\) 随 \(n\) 增大而变小，所以 \(r(n)\) 单调上升，并且永远小于 \(\frac12\)。于是上界取 \(c_2=\frac12\) 一劳永逸。 第三步，下界要求 \(r(n)\) 为正且离 0 有距离。\(n=6\) 时 \(r=0\)，不行；\(n=7\) 时 \(r=\frac1{14}\)，之后只会更大。所以从 \(n_0=7\) 起取 \(c_1=\frac1{14}\)。 换个更省事的取法也行：\(n\ge12\) 时 \(\frac3n\le\frac14\)，\(r(n)\ge\frac14\)，可取 \(c_1=\frac14\)、\(n_0=12\)。定义只要求"找得到"，不要求最好。 对照 \(n\) 翻倍：\(n=100\) 时 \(f=4700\)，\(n=200\) 时 \(f=19400\)，约 4.1 倍，接近 \(n^2\) 的 4 倍；\(n\) 越大越接近 4。

例 2：\(6n^3\ne\Theta(n^2)\)。 若存在 \(c_2\)、\(n_0\) 使 \(6n^3\le c_2n^2\) 对所有 \(n\ge n_0\) 成立，则 \(n\le c_2/6\)，对足够大的 \(n\) 不可能。

直觉。 低阶项可以忽略，因为 \(n\) 大时最高阶项的一小部分就能压过它们；取 \(c_1\) 略小于、\(c_2\) 略大于最高阶系数即可。最高阶系数本身也可忽略，它只按常数比例改变 \(c_1\)、\(c_2\)。对二次函数 \(f(n)=an^2+bn+c\)（\(a>0\)），取 \(c_1=a/4\)、\(c_2=7a/4\)、\(n_0=2\max(|b|/a,\sqrt{|c|/a})\) 即可。一般地，若 \(p(n)=\sum_{i=0}^da_in^i\) 且 \(a_d>0\)，则 \(p(n)=\Theta(n^d)\)。常数是 0 次多项式，记为 \(\Theta(1)\)。

\(O\)：渐近上界

\(\Theta\) 比 \(O\) 强：\(\Theta(g(n))\subseteq O(g(n))\)。例如 \(a>0\) 时任何线性函数 \(an+b\) 都属于 \(O(n^2)\)（取 \(c=a+|b|\)、\(n_0=\max(1,-b/a)\)）。本书中 \(f(n)=O(g(n))\) 只声称 \(g\) 的某个常数倍是上界，不声称上界有多紧。文献中有人非正式地用 \(O\) 表示紧确界，但算法文献里区分二者是标准做法。

只看算法的整体结构常常就能得到 \(O\) 上界。插入排序是双重循环，内层每次迭代 \(O(1)\)，下标 \(i\)、\(j\) 都不超过 \(n\)，所以最坏 \(O(n^2)\)。

"运行时间是 \(O(n^2)\)"的确切含义。 同一个 \(n\) 下运行时间随输入变化，所以这句话严格说是滥用。它的意思是：存在 \(f(n)\in O(n^2)\)，使得对任意 \(n\)、任意规模为 \(n\) 的输入，运行时间都不超过 \(f(n)\)；等价于"最坏运行时间是 \(O(n^2)\)"。注意反方向不成立：插入排序最坏是 \(\Theta(n^2)\)，并不意味着每个输入都要 \(\Theta(n^2)\)，已排序输入只要 \(\Theta(n)\)。

\(\Omega\)：渐近下界

定理 3.1 对任意两个函数 \(f(n)\)、\(g(n)\)，\(f(n)=\Theta(g(n))\) 当且仅当 \(f(n)=O(g(n))\) 且 \(f(n)=\Omega(g(n))\)。

实践中常用它由上下界合成紧确界。说"运行时间是 \(\Omega(g(n))\)"，意思是无论选哪个规模为 \(n\) 的输入，运行时间至少是 \(g(n)\) 的常数倍，等价于最好情况的下界。插入排序运行时间是 \(\Omega(n)\) 且 \(O(n^2)\)，两个界都尽可能紧：它的运行时间不是 \(\Omega(n^2)\)（有输入只需 \(\Theta(n)\)），但"最坏运行时间是 \(\Omega(n^2)\)"是对的。练习 3.1-6 把这一点一般化：运行时间为 \(\Theta(g(n))\) 当且仅当最坏运行时间为 \(O(g(n))\) 且最好运行时间为 \(\Omega(g(n))\)。

练习 3.1-3 问"算法 A 的运行时间至少是 \(O(n^2)\)"为何无意义：\(O\) 是上界，"至少是某个上界"不提供任何信息。这种说法在技术文档里很常见，要避免。

白话解释：最坏情况、最好情况和 \(O\)、\(\Omega\)、\(\Theta\) 是两件不同的事，容易搅在一起。前者问"挑哪种输入"，后者问"界有多紧"。用插入排序对一下： 已排好序的输入（最好情况）：耗时 \(\Theta(n)\)，数据翻倍耗时翻 2 倍。 逆序输入（最坏情况）：耗时 \(\Theta(n^2)\)，数据翻倍耗时翻 4 倍。 不指定输入，笼统说"运行时间"：只能说它在 \(\Omega(n)\) 和 \(O(n^2)\) 之间，翻倍时耗时在 2 倍到 4 倍之间，取决于数据的样子。 这像描述一只债券基金的久期：说"久期不超过 7 年"（\(O\)）和"久期至少 3 年"（\(\Omega\)）都是真话，但只有"久期约 5 年"（\(\Theta\)）才精确刻画了它。说"久期至少不超过 7 年"就是一句空话。

等式中的渐近记号

• 单独出现在等号右边，如 \(n=O(n^2)\)，等号表示集合成员关系。
• 出现在更大的公式中，表示某个不愿写出名字的匿名函数（anonymous function）。\(2n^2+3n+1=2n^2+\Theta(n)\) 表示存在 \(f(n)\in\Theta(n)\)（这里 \(f(n)=3n+1\)）使等式成立。归并排序的递归式 \(T(n)=2T(n/2)+\Theta(n)\) 正是这样省掉了无关细节。
• 匿名函数的个数等于记号出现的次数。\(\sum_{i=1}^nO(i)\) 只有一个匿名函数（关于 \(i\) 的函数），它不同于 \(O(1)+O(2)+\cdots+O(n)\)，后者没有清晰的解释。
• 出现在等号左边，如 \(2n^2+\Theta(n)=\Theta(n^2)\)，规则是：无论左边的匿名函数怎么取，都能选到右边的匿名函数使等式成立。等号右边比左边更粗糙。可以链式使用：\(2n^2+3n+1=2n^2+\Theta(n)=\Theta(n^2)\)。

白话解释：这里的"等号"不是真的相等，而是"左边可以被右边描述"，是单向的。把 \(\Theta(n)\) 想成一个打了马赛克的项：\(2n^2+\Theta(n)\) 的意思是"\(2n^2\) 加上某个大约和 \(n\) 成正比的东西，具体是什么不重要"。这和财报附注里写"其他费用"类似：你知道它有，量级可控，但不逐项列出。 正因为是单向的，\(n=O(n^2)\) 可以写，反过来写 \(O(n^2)=n\) 就错了；同样，\(\Theta(n^2)=2n^2+\Theta(n)\) 也不成立（\(\Theta(n^2)\) 里有 \(3n^2\)，它不是 \(2n^2\) 加一个线性项）。读递归式 \(T(n)=2T(n/2)+\Theta(n)\) 时，就读成"排 \(n\) 个数的时间 = 两个子问题的时间 + 一笔和 \(n\) 成正比的合并费用"。

\(o\) 与 \(\omega\)：非紧确的界

与 \(O\) 的区别在量词：\(O\) 要求"存在某个" \(c\)，\(o\) 要求"对所有" \(c>0\)。直观上 \(f\) 相对 \(g\) 变得可以忽略：

例：\(2n=o(n^2)\)，但 \(2n^2\ne o(n^2)\)；\(n^2/2=\omega(n)\)，但 \(n^2/2\ne\omega(n^2)\)。\(f\in\omega(g)\) 当且仅当 \(g\in o(f)\)。

推导拆解：为什么 \(2n=o(n^2)\)？按定义，对任意给定的 \(c>0\)（哪怕 \(c=0.001\)），都要找到 \(n_0\) 使 \(n\ge n_0\) 时 \(2n<cn^2\)。两边除以 \(n\) 得 \(2<cn\)，即 \(n>2/c\)。所以取 \(n_0=\lfloor 2/c\rfloor+1\) 就行：\(c=0.001\) 时 \(n_0=2001\)。\(c\) 越小，\(n_0\) 越靠后，但总找得到。 为什么 \(2n^2\ne o(n^2)\)？取 \(c=1\)，要求 \(2n^2<n^2\)，对任何 \(n\ge1\) 都不成立。\(O\) 只要求"某一个"\(c\) 能管住，\(o\) 要求"每一个"\(c\) 都能管住，所以 \(o\) 严格得多。 用翻倍的语言：\(f=o(g)\) 时，比值 \(f/g\) 会一路缩向 0，规模越大，\(f\) 在 \(g\) 面前越不值一提；\(f=\Theta(g)\) 时，比值稳定在两个正数之间。这里的 \(o\) 和统计里"\(o_p(1)\)（依概率趋于 0）"是同一个意思的不同版本。

函数比较的性质

设 \(f\)、\(g\) 渐近为正：

• 传递性：五种记号都满足，如 \(f=O(g)\) 且 \(g=O(h)\) 推出 \(f=O(h)\)。
• 自反性：\(f=\Theta(f)\)，\(f=O(f)\)，\(f=\Omega(f)\)。
• 对称性：\(f=\Theta(g)\iff g=\Theta(f)\)。
• 转置对称性：\(f=O(g)\iff g=\Omega(f)\)；\(f=o(g)\iff g=\omega(f)\)。

可以把它们类比为实数比较：\(O\sim\le\)，\(\Omega\sim\ge\)，\(\Theta\sim=\)，\(o\sim<\)，\(\omega\sim>\)。但三分性不成立：并非任意两个函数都能比较。\(n\) 与 \(n^{1+\sin n}\) 就不可比，后者的指数在 0 到 2 之间振荡，既不是 \(O(n)\) 也不是 \(\Omega(n)\)。

3.3 标准记号与常用函数

单调性、取整与模运算

\(m\le n\Rightarrow f(m)\le f(n)\) 称单调递增；\(m<n\Rightarrow f(m)<f(n)\) 称严格递增；递减类似。

\(\lfloor x\rfloor\) 是不超过 \(x\) 的最大整数，\(\lceil x\rceil\) 是不小于 \(x\) 的最小整数：

对任意整数 \(n\)，\(\lceil n/2\rceil+\lfloor n/2\rfloor=n\)。对实数 \(x\ge0\)、整数 \(a,b>0\)：

前两式在第 04b 章处理递归式中的取整时会用到。

模运算（modular arithmetic）：对整数 \(a\) 和正整数 \(n\)，\(a\bmod n=a-n\lfloor a/n\rfloor\)，满足 \(0\le a\bmod n<n\)。若 \(a\bmod n=b\bmod n\)，记 \(a\equiv b\pmod n\)，等价于 \(n\) 整除 \(b-a\)。量化系统里最常见的用法是环形缓冲区（ring buffer）：长度为 \(w\) 的滚动窗口用一个定长数组保存，第 \(t\) 个观测写到位置 \(t\bmod w\)，覆盖掉恰好滑出窗口的旧值，不需要移动任何元素。

多项式与指数

\(d\) 次多项式 \(p(n)=\sum_{i=0}^da_in^i\)（\(a_d\ne0\)）渐近为正当且仅当 \(a_d>0\)，此时 \(p(n)=\Theta(n^d)\)。若存在常数 \(k\) 使 \(f(n)=O(n^k)\)，称 \(f\) 多项式有界（polynomially bounded）。

指数满足 \(a^0=1\)、\((a^m)^n=a^{mn}\)、\(a^ma^n=a^{m+n}\)，约定 \(0^0=1\)。关键结论是：对实常数 \(a>1\) 与任意 \(b\)，

底数大于 1 的指数函数比任何多项式增长都快。

金融直觉：这就是复利打败单利的数学版。看"\(n\) 加 1 时增长了多少倍"：\(n^b\) 从 \(n\) 到 \(n+1\) 只乘了 \((1+\frac1n)^b\)，\(n\) 越大这个倍数越接近 1，好比收益率在不断递减；\(a^n\) 每一步都稳定乘 \(a\)，好比固定复利。哪怕 \(b=100\)、\(a=1.01\)，前面一大段 \(n^{100}\) 遥遥领先，但当 \((1+\frac1n)^{100}\) 跌到 1.01 以下（约 \(n>10^4\)）之后，\(1.01^n\) 每步都涨得更多，终究会反超并把差距拉到无穷大。

自然对数的底 \(e=2.71828\ldots\)：

\(x\to0\) 时 \(e^x=1+x+\Theta(x^2)\)（这里渐近记号描述 \(x\to0\) 的行为），并且对所有 \(x\)，

这是连续复利的数学基础：年利率 \(x\)，一年复利 \(n\) 次，\(n\to\infty\) 时本息和趋于 \(e^x\)。不等式 \(1+x\le e^x\) 在第 05 章分析生日悖论时还会用到。

对数

记号：\(\lg n=\log_2n\)，\(\ln n=\log_en\)，\(\lg^kn=(\lg n)^k\)（幂），\(\lg\lg n=\lg(\lg n)\)（复合）。约定对数只作用于紧跟的项，\(\lg n+k\) 表示 \((\lg n)+k\)。常用恒等式（\(a,b,c>0\)，底数不为 1）：

换底公式说明不同底的对数只差常数因子，所以在 \(O\) 记号里一律写 \(\lg n\)。计算机科学偏爱底 2，因为很多算法把问题一分为二。

推导拆解：最后一个恒等式 \(a^{\log_bc}=c^{\log_ba}\) 在第 04b 章主定理里反复出现（如 \(n^{\log_ba}\) 与 \(a^{\log_bn}\) 互换），值得会推。两边同时取 \(\log_b\)：左边 \(\log_b\big(a^{\log_bc}\big)=\log_bc\cdot\log_ba\)（用了 \(\log x^k=k\log x\)）；右边 \(\log_b\big(c^{\log_ba}\big)=\log_ba\cdot\log_bc\)。两边相等，而对数是一一对应的，所以原式相等。数值检查：\(a=4\)、\(b=2\)、\(c=8\)，左边 \(4^{\lg8}=4^3=64\)，右边 \(8^{\lg4}=8^2=64\)。 换底公式的含义：\(\ln n=\lg n\cdot\ln2\approx0.693\lg n\)，两者永远差同一个倍数，所以 \(\Theta(\ln n)=\Theta(\lg n)=\Theta(\log_{10}n)\)，渐近记号里底数无关紧要。但注意，指数位置上的底数不能随便换：\(2^n\) 与 \(4^n\) 不是同阶（见 3.4 节）。

对 \(x>-1\)：

若 \(f(n)=O(\lg^kn)\)，称 \(f\) 多对数有界（polylogarithmically bounded）。在 \(n^b=o(a^n)\) 中用 \(\lg n\) 代 \(n\)、用 \(2^a\) 代 \(a\)，得 \(\lg^bn=o(n^a)\) 对任意常数 \(a>0\) 成立：任何正幂多项式都比任何多对数函数增长快。

阶乘

\(n!=1\cdot2\cdots n\)，\(0!=1\)。弱上界 \(n!\le n^n\)。Stirling 近似：

由此得 \(n!=o(n^n)\)，\(n!=\omega(2^n)\)，以及

推导拆解：\(\lg(n!)=\Theta(n\lg n)\) 不用 Stirling 也能看出来。\(\lg(n!)=\lg1+\lg2+\cdots+\lg n\)（乘积的对数 = 对数之和）。 上界：每一项都不超过 \(\lg n\)，共 \(n\) 项，所以 \(\lg(n!)\le n\lg n\)。 下界：只保留后一半，即从 \(n/2\) 到 \(n\) 的那些项，每项至少 \(\lg(n/2)\)，大约有 \(n/2\) 项，所以 \(\lg(n!)\ge\frac n2\lg\frac n2=\frac n2(\lg n-1)\)，当 \(n\ge4\) 时这至少是 \(\frac14n\lg n\)。 上下界都是 \(n\lg n\) 的常数倍，由定理 3.1 得 \(\Theta(n\lg n)\)。直观意义：要从 \(n!\) 种可能的排列里认出唯一正确的那个，每次比较只能回答"是/否"，相当于每次最多排除一半候选，至少要问 \(\lg(n!)\) 次。

最后一式很重要：第 8 章证明比较排序下界 \(\Omega(n\lg n)\) 时，用的就是"\(n!\) 个排列需要 \(\lg(n!)\) 次二元比较来区分"。更精确的 Robbins 界是 \(n!=\sqrt{2\pi n}(n/e)^ne^{\alpha_n}\)，\(\frac1{12n+1}<\alpha_n<\frac1{12n}\)。

迭代对数与斐波那契数

函数迭代：\(f^{(0)}(n)=n\)，\(f^{(i)}(n)=f(f^{(i-1)}(n))\)。迭代对数（iterated logarithm）

即反复取对数直到不超过 1 所需的次数。注意区分 \(\lg^{(i)}n\)（取 \(i\) 次对数）与 \(\lg^in\)（对数的 \(i\) 次幂）。它增长极慢：\(\lg^*2=1\)，\(\lg^*4=2\)，\(\lg^*16=3\)，\(\lg^*65536=4\)，\(\lg^*(2^{65536})=5\)。可观测宇宙的原子数约 \(10^{80}\)，远小于 \(2^{65536}\)，所以实际中 \(\lg^*n\) 不会超过 5。并查集等数据结构的复杂度里会出现这类函数，实践中可以把它当成常数。

斐波那契数：\(F_0=0\)，\(F_1=1\)，\(F_i=F_{i-1}+F_{i-2}\)。设 \(\phi=\frac{1+\sqrt5}{2}=1.61803\ldots\)（黄金分割率）、\(\hat\phi=\frac{1-\sqrt5}{2}=-0.61803\ldots\)，二者是 \(x^2=x+1\) 的根，且

由于 \(|\hat\phi^i|/\sqrt5<1/2\)，\(F_i=\lfloor\phi^i/\sqrt5+\frac12\rfloor\)，即 \(\phi^i/\sqrt5\) 四舍五入，斐波那契数指数增长。

增长量级阶梯

把本章的函数按增长从慢到快排列（\(\epsilon>0\)、\(k\ge1\)、\(c>1\) 为常数）：

比较两个陌生函数时，常用三招：取对数后比较（如 \((\lg n)^{\lg n}\) 与 \(n^{\lg\lg n}\)，取对数都是 \(\lg n\cdot\lg\lg n\)，所以相等）；用恒等式化简（\(2^{\lg n}=n\)，\(4^{\lg n}=n^2\)，\(n^{1/\lg n}=2\)，\(n^{\lg c}=c^{\lg n}\)）；用 Stirling 公式处理阶乘（\(\lg(n!)=\Theta(n\lg n)\)）。原书思考题 3-3 要求给 30 个函数排序，是这方面最好的练习。

3.4 几个容易混淆的判断

原书思考题 3-4 把常见误区集中成真假题（\(f\)、\(g\) 渐近为正）：

第四行值得量化开发者记住：指数里的常数不能随便丢。\(2^{2n}=4^n\) 不是 \(O(2^n)\)（练习 3.1-4），而 \(2^{n+1}=2\cdot2^n\) 是。穷举 \(n\) 个资产的所有子集（\(2^n\)）和穷举 \(2n\) 个资产的所有子集（\(4^n\)），差别不是常数倍。

原书思考题 3-5 还介绍了软 O 记号（soft-oh）\(\tilde O(g(n))\)：忽略多对数因子的 \(O\)，即存在 \(k\) 使 \(f(n)=O(g(n)\lg^kn)\)。读论文时会经常遇到。

量化实战：用增长率估算系统成本，用增量算法降阶

给量化流程估算复杂度

设股票数 \(N\)、时间点数 \(T\)、因子数 \(K\)。常见环节的成本：

从 300 只股票扩到 3000 只，\(N^3\) 的求逆成本涨 1000 倍，\(N^2T\) 的协方差涨 100 倍，截面排序只涨约 13 倍。这是为什么大股票池几乎都用因子模型（\(K\ll N\)）而不是样本协方差，也是为什么先估算增长率、再考虑换语言或加机器。

滚动窗口统计：从 \(\Theta(nw)\) 到 \(\Theta(n)\)

滚动均值的朴素实现对每个窗口重新求和，代价 \(\Theta(w)\)，总计 \(\Theta(nw)\)。增量实现维护窗口和 \(s\)：新值进来加上，滑出的旧值减去，每步 \(O(1)\)，总计 \(\Theta(n)\)。方差同理，再维护平方和。滚动中位数没有这么简单的增量公式，可以维护一个有序窗口：用二分查找定位、插入新值并删除旧值，这正是插入排序的一步。

判断实现的真实复杂度，最直接的方法是测 log-log 斜率：若运行时间 \(\approx cw^k\)，则 \(\ln t\approx\ln c+k\ln w\)，对 \((\ln w,\ln t)\) 做线性回归，斜率就是 \(k\) 的估计。

金融直觉：log-log 斜率就是"弹性"：规模变动 1%，耗时变动百分之几。这和用对数需求对对数价格回归求价格弹性是同一个做法，斜率 \(k\) 回答的正是"数据翻倍耗时翻几倍"：翻 \(2^k\) 倍。斜率 1 意味着翻 2 倍，斜率 2 意味着翻 4 倍，斜率 0 意味着不变。\(n\lg n\) 在常见规模上的斜率会略大于 1（比如 1.05～1.1），不必误判为二次。

代码说明：增量版的核心只有两行，s += xt 把新值加进窗口和，s -= old 把滑出窗口的旧值减掉，所以窗口再长每步也只做常数次运算。方差公式 \(\frac{s_2-s^2/w}{w-1}\) 就是你熟悉的样本方差 \(\frac{1}{w-1}\big(\sum x^2-w\bar x^2\big)\) 换了个写法。bisect.insort(win, xt) 用二分查找在有序列表里找到插入位置再插入；np.polyfit(x, y, 1)[0] 是对 \(y\) 关于 \(x\) 做一元线性回归并取斜率。

import time, bisect
import numpy as np, pandas as pd

def rolling_mean_naive(x, w):            # 每个窗口重新求和：Θ(n·w)
    out = np.full(len(x), np.nan)
    for t in range(w - 1, len(x)):
        s = 0.0
        for k in range(t - w + 1, t + 1):
            s += x[k]
        out[t] = s / w
    return out

def rolling_mean_var_incr(x, w):         # 增量更新：Θ(n)，与 w 无关
    m = np.full(len(x), np.nan); v = np.full(len(x), np.nan)
    s = s2 = 0.0
    for t, xt in enumerate(x):
        s += xt; s2 += xt * xt
        if t >= w:                        # 移出窗口最左端的旧值
            old = x[t - w]; s -= old; s2 -= old * old
        if t >= w - 1:
            m[t] = s / w
            v[t] = (s2 - s * s / w) / (w - 1)   # 样本方差
    return m, v

def rolling_median_insort(x, w):         # 维护有序窗口：插入/删除各 O(w)
    win, out = [], np.full(len(x), np.nan)
    for t, xt in enumerate(x):
        bisect.insort(win, xt)            # 二分找位置 + 插入（插入排序的一步）
        if t >= w:
            del win[bisect.bisect_left(win, x[t - w])]
        if t >= w - 1:
            out[t] = win[w // 2] if w % 2 else 0.5 * (win[w//2 - 1] + win[w//2])
    return out

rng = np.random.default_rng(0)
r = rng.standard_normal(5000) * 0.01      # 模拟日收益
w = 60
ref = pd.Series(r).rolling(w)
m, v = rolling_mean_var_incr(r, w)
print("均值误差", np.nanmax(abs(m - ref.mean().values)),
      "方差误差", np.nanmax(abs(v - ref.var().values)),
      "中位数误差", np.nanmax(abs(rolling_median_insort(r, w) - ref.median().values)))

# 经验复杂度：固定 n，改变窗口 w，用 log-log 斜率估计运行时间对 w 的幂次
def timeit(f, *a):
    t0 = time.perf_counter(); f(*a); return time.perf_counter() - t0
x = rng.standard_normal(4000)
ws = [25, 50, 100, 200, 400]
tn = [timeit(rolling_mean_naive, x, w) for w in ws]
ti = [timeit(rolling_mean_var_incr, x, w) for w in ws]
for w, a, b in zip(ws, tn, ti):
    print(f"w={w:4d}  朴素 {a*1e3:8.1f} ms   增量 {b*1e3:6.1f} ms")
slope = lambda t: np.polyfit(np.log(ws), np.log(t), 1)[0]
print(f"对 w 的斜率: 朴素 {slope(tn):.2f}, 增量 {slope(ti):.2f}")

# 对数收益与简单收益：x/(1+x) <= ln(1+x) <= x  (式 3.17)
for x_ in [-0.10, -0.02, 0.02, 0.10]:
    print(f"x={x_:+.2f}: x/(1+x)={x_/(1+x_):+.5f}  ln(1+x)={np.log1p(x_):+.5f}  x={x_:+.5f}")

输出（计时数字随机器而变，斜率稳定）：

均值误差 1.0408340855860843e-17 方差误差 1.1655173354219173e-18 中位数误差 0.0
w=  25  朴素      4.6 ms   增量    1.3 ms
w=  50  朴素      9.7 ms   增量    1.2 ms
w= 100  朴素     18.9 ms   增量    1.2 ms
w= 200  朴素     35.9 ms   增量    1.1 ms
w= 400  朴素     68.5 ms   增量    1.1 ms
对 w 的斜率: 朴素 0.97, 增量 -0.08
x=-0.10: x/(1+x)=-0.11111  ln(1+x)=-0.10536  x=-0.10000
x=-0.02: x/(1+x)=-0.02041  ln(1+x)=-0.02020  x=-0.02000
x=+0.02: x/(1+x)=+0.01961  ln(1+x)=+0.01980  x=+0.02000
x=+0.10: x/(1+x)=+0.09091  ln(1+x)=+0.09531  x=+0.10000

几点说明：

• 朴素实现的斜率约 1，说明耗时与 \(w\) 成正比；增量实现斜率约 0，与 \(w\) 无关。三种增量结果与 pandas 一致。
• 用"平方和减和的平方"算方差在数值上有风险：若数据均值远大于标准差（例如直接对价格而不是收益算），两项几乎相等，相减会丢失有效数字（灾难性抵消）。实务中对价格应先减去一个参考值，或改用 Welford 型的滑动更新。复杂度分析不告诉你这一点，这是 RAM 模型"不关心精度"的代价。
• 有序窗口的滚动中位数每步是 \(O(w)\)（列表插入要移动元素，只是由 C 层的内存移动完成，常数很小）。用两个堆或平衡树可以做到每步 \(O(\lg w)\)，见本册后续堆与红黑树的章节。
• 最后四行验证了 (3.17)：对数收益 \(\ln(1+x)\) 被简单收益 \(x\) 和 \(x/(1+x)\) 夹住。\(|x|=2\%\) 时两种收益相差约 \(0.0002\)，\(|x|=10\%\) 时相差约 \(0.005\)，大波动日不能把两者混用。

本章小结

渐近记号用来描述函数在自变量趋于无穷时的增长：\(\Theta\) 是紧确界，\(O\) 是上界，\(\Omega\) 是下界，\(o\)、\(\omega\) 是严格的上下界（比值极限为 0 或 \(\infty\)），\(\Theta\) 成立当且仅当 \(O\) 与 \(\Omega\) 同时成立。"运行时间是 \(O(g)\)"等于说最坏情况是 \(O(g)\)，"运行时间是 \(\Omega(g)\)"等于说最好情况是 \(\Omega(g)\)。公式中的渐近记号代表匿名函数，出现在等号左边时，右边是更粗糙的描述。比较函数增长时，记住阶梯 \(\lg^*n\ll\lg n\ll n^\epsilon\ll n\ll n\lg n\ll n^2\ll c^n\ll n!\)，并善用取对数、对数恒等式与 Stirling 公式。在量化系统中，先按 \(N\)、\(T\)、\(K\)、\(w\) 估算各环节增长率，再用 log-log 斜率实测验证，找到真正的瓶颈后再做优化。

练习

基础

1. 用 \(\Theta\) 的定义证明 \(\max(f(n),g(n))=\Theta(f(n)+g(n))\)。 提示：\(\frac12(f+g)\le\max(f,g)\le f+g\)。
2. 证明对实常数 \(a\) 和 \(b>0\)，\((n+a)^b=\Theta(n^b)\)。 提示：\(n\ge2|a|\) 时 \(n/2\le n+a\le2n\)。
3. \(2^{n+1}=O(2^n)\) 成立吗？\(2^{2n}=O(2^n)\) 呢？ 答案：前者成立（\(=2\cdot2^n\)）；后者不成立（比值 \(2^n\to\infty\)）。
4. 证明 \(o(g(n))\cap\omega(g(n))=\varnothing\)。
5. 用 Stirling 公式证明 \(\lg(n!)=\Theta(n\lg n)\)，并证明 \(n!=\omega(2^n)\)、\(n!=o(n^n)\)。
6. 判断下列每对 \((A,B)\) 中 \(A\) 是否为 \(B\) 的 \(O\)、\(o\)、\(\Omega\)、\(\omega\)、\(\Theta\)（\(k\ge1\)、\(\epsilon>0\)、\(c>1\)）：\(\lg^kn\) 与 \(n^\epsilon\)；\(n^k\) 与 \(c^n\)；\(\sqrt n\) 与 \(n^{\sin n}\)；\(2^n\) 与 \(2^{n/2}\)；\(n^{\lg c}\) 与 \(c^{\lg n}\)；\(\lg(n!)\) 与 \(\lg(n^n)\)。 答案：依次为 \(o\)（也是 \(O\)）；\(o\)；都不成立（不可比）；\(\omega\)（也是 \(\Omega\)）；\(\Theta\)；\(\Theta\)。

进阶

7. \(\lceil\lg n\rceil!\) 是否多项式有界？\(\lceil\lg\lg n\rceil!\) 呢？ 答案：前者否，\(\lg(\lceil\lg n\rceil!)=\Theta(\lg n\lg\lg n)\ne O(\lg n)\)；后者是，\(\lg(\lceil\lg\lg n\rceil!)=\Theta(\lg\lg n\cdot\lg\lg\lg n)=o(\lg n)\)。
8. \(\lg(\lg^*n)\) 与 \(\lg^*(\lg n)\) 哪个渐近更大？ 答案：\(\lg^*(\lg n)=\lg^*n-1\)，而 \(\lg(\lg^*n)\) 远小于 \(\lg^*n\)，所以后者更大。
9. 证明 \(k\ln k=\Theta(n)\) 蕴含 \(k=\Theta(n/\ln n)\)。（这类"反解"在估计"给定计算预算能处理多大的 \(n\)"时常用。）
10. 量化应用：某因子研究流程在 \(N=500\) 时耗时 2 分钟，其中 70% 在协方差求逆（\(O(N^3)\)），30% 在截面排序（\(O(N\lg N)\)）。估算 \(N=4000\) 时的耗时，并指出应优先优化哪一环。 提示：求逆部分放大 \(8^3=512\) 倍，约 717 分钟；排序部分约放大 \(8\times\lg4000/\lg500\approx10.7\) 倍，约 6.4 分钟。应先把求逆换成因子模型或低秩近似。

原书推荐习题：3.1-3、3.1-4（辨析 \(O\) 的含义与误用）；3.2-3（Stirling 公式，第 8 章排序下界要用）；思考题 3-2、3-3（系统比较增长率，3-3 是经典难题）；思考题 3-4（渐近记号性质真假判断）；思考题 3-6（迭代函数 \(f_c^*\)，如 \(\sqrt n\) 降到 2 需 \(\lg\lg n\) 次）。

原书对照