Sherfiter's wiki for fun

第 1 章 · 复杂度分析

复杂度分析最容易学成「背记号」,所以这门课从一次真实的跑分开始。同一个「找出所有和为零的数对」问题,两种解法:

// 解法一:双重循环,逐对检查
int pairs1(int *a, int n) {
    int c = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == 0) c++;
    return c;
}
// 解法二:哈希集合,对每个数查它的相反数在不在(第 7 章实现哈希表)

同一台机器,不同数据规模下的真实耗时:

n=1,000    解法一  2 ms    解法二  1 ms     差 2 倍,无感
n=100,000  解法一  18 s    解法二  120 ms   差 150 倍
n=1,000,000 解法一 约 30 分钟  解法二  1.3 s    不是同一物种了

n 扩大一千倍,解法一慢了一万倍(n² 的特性),解法二只慢一千倍。复杂度分析就是预测这件事的数学:n 变大时,运行时间按什么速率增长。它帮你在大规模数据到来之前,就知道哪段代码会在压测里爆炸。本章把大 O 记号、三个「最好最坏平均」、摊还分析这套工具讲扎实,它是后面全部章节的度量衡。

1.1 大 O:只关心增长速率

大 O 记号给运行时间一个「增长量级」:基本操作次数 T(n) = 2n² + 3n + 5,当 n 巨大时,2n² 完全主导,其他项都可以忽略,记作 O(n²)。三条化简规则:丢常数系数(2n² → n²)、丢低阶项(3n)、只留主导项。严格定义(T(n) ≤ c·f(n) 对足够大的 n 成立)教材会考,直觉上记住一句话就够:大 O 回答「n 翻倍,时间翻几倍」:O(n) 翻倍,O(n²) 翻四倍,O(log n) 只加一格,O(2ⁿ) 直接爆炸。

一张按真实体感校准过的表(n = 一百万时的操作次数,按每秒十亿次操作折算耗时):

阶n=10⁶ 的操作数体感耗时典型算法
O(1)1瞬间数组下标、哈希查找
O(log n)~20瞬间二分查找、平衡树
O(n)10⁶~1 ms一趟遍历
O(n log n)~2×10⁷~20 ms排序(快/归/堆)
O(n²)10¹²~20 分钟双重循环、冒泡
O(2ⁿ)天文数字宇宙热寂穷举子集

「O(n log n) 是排序的下界」这类结论、以及「竞赛里 10⁸ 次基本操作约 1 秒」这条经验线,都从这张表长出来。写题前先算规模 × 复杂度,不超过 10⁸ 量级再动手,能省下大量「TLE 后回头换算法」的时间。

1.2 最好、平均、最坏:同一算法的三张面孔

同一个顺序查找,目标在第一位 O(1),不在表里 O(n),随机位置平均 n/2 次。为什么分开谈?因为它们回答不同的问题:最坏情况是承诺(「再倒霉也不会比这差」,服务器性能评估必须按最坏算),平均情况是期望(「正常日子跑多快」,但依赖输入分布假设,快排的平均 O(n log n) 建立在「切分点大致随机」上,构造出的恶意输入能把它逼到 O(n²),这是快排要随机选 pivot 的原因)。

工程和竞赛的第一直觉都是先看最坏,但有一个著名例外:哈希表。它的最坏是 O(n)(全部键撞进一个桶),平均 O(1),全行业普遍接受这个赌注,靠散列函数的随机性把最坏概率压到可忽略。记住这个例外,第 7 章实现哈希表时你会亲手算「负载因子」怎么保证这个赌注不输。

1.3 摊还分析:偶尔贵一次,总体仍然便宜

有些操作「偶尔很贵,平时很便宜」,单看最坏会高估。动态数组(可扩容的数组)是标本:平时 append 是 O(1),数组满了要搬家——分配两倍大数组、全体搬运一次,O(n)。乍看最坏是 O(n),很吓人;摊还分析把「搬家的大开销」平摊到「促成搬家的那 n 次便宜操作」头上:

从空数组连续 append n 次:
  搬家发生在容量 1,2,4,8,...,n 处,总搬运 1+2+4+...+n < 2n 次
  总开销 < 2n + n(append 本体) = O(n)
  平摊到每次 append:O(1)

结论:连续 n 次 append 总共 O(n),均摊每次 O(1)。哈希表的扩容再散列、C++ vector 的 push_back,全是同一个模式。摊还 O(1) 和「每次都 O(1)」的区别在实时系统里是致命的(某一次操作突然 100ms),但在一般应用里,这个赌和哈希表的赌一样划算。本章之后,「摊还」这个词会在线性表和哈希表两章反复出现。

1.4 空间复杂度:另一本账

空间复杂度数额外内存(不含输入本身)。原地排序(冒泡、快排)额外 O(1),归并排序要 O(n) 辅助数组,快排递归栈 O(log n) 起步(坏情况 O(n))。空间换时间是永恒的交易:哈希表用 O(n) 空间买 O(1) 查找;反过来,用 O(1) 空间多花时间的算法也存在(Floyd 判圈)。递归算法特别注意:递归深度就是栈空间,「深度 n 的递归」哪怕一行额外变量都不申请,空间也是 O(n),爆栈(计组第 10 章讲过栈只有 8MB)就是这么来的。

常见错误

  • 只数循环层数。for(i=0;i<n;i++) for(j=i;j<n;j+=i) 看着两层,n 次内层循环按调和级数收缩,总操作约 n·ln n,不是 n²。数基本操作总次数,别数循环。
  • 忽略隐藏常数。O(n log n) 的排序输给 O(n²) 的插入排序,在小规模(比如 n 小于 50)和常数巨大(比较函数是函数指针)时都真实发生。复杂度决定「数量级」,常数决定「同数量级内胜负」,两者都别丢。
  • 递归复杂度只数调用次数。每次调用里的循环、以及子问题分裂成几个,都要进递推式(T(n) = 2T(n/2) + O(n) → O(n log n),第 9 章递归章会系统讲主定理)。

练习

  1. 手算:分析下面代码的时间复杂度,写出推导过程:for (i=0; i<n; i*=2) { for (j=0; j<n; j++) work(); }(答案应为 O(n log n),说明外层跑几次。)
  2. 手算:1.3 节的动态数组,若扩容改为「每次加 10」而不是「翻倍」,连续 append n 次的总开销变成多少?说明为什么「加常数」的扩容策略是错的。
  3. 动手:复现开头实验(用 rand 生成数据,哈希解法可先用 C 的 qsort + 二分解法替代),n 取 10³/10⁴/10⁵,把两组耗时记成表,验证「n 翻倍时间如何变化」的理论。
  4. 思考:「平均 O(1) 但最坏 O(n)」的哈希表,和「保证 O(log n)」的平衡树,什么时候你会选后者?(提示:路由表、证券交易这类「响应时间必须有上界」的场景。)
豫ICP备2026027944号