算法复杂度与大 O：一把尺子量遍前面所有算法

引言：前面 11 章的算法，到底谁快谁慢

阶段 3 我们写了一堆东西：链表、栈、队列、动态数组、二叉树、BST、哈希表，还有冒泡/插入/选择/快排/归并五种排序、线性查找和二分查找。每一种都「能用」，可一旦数据量大起来——比如要在一百万个元素里找一个数、给十万个数排序——选错结构或算法，速度能差几千几万倍。这一章就给前面所有算法配一把统一的尺子：大 O 记号（big-O notation），它描述「算法的运行时间（或空间）怎么随输入规模 n 增长」。掌握它，你才能在面对一个问题时，挑出「快」的那条路、躲开「慢」的坑。这是阶段 3 的收口章。

大 O 是什么：看趋势，不看常数

大 O 记号描述的是渐进复杂度（asymptotic complexity）——当 n 趋向很大时，算法耗时的增长趋势的上界。它有两个关键特点：只看 n 趋向无穷的趋势、忽略常数和低阶项。比如一个算法耗时 $3 n ² + 5 n + 100$ 次，大 O 就是 $O (n ²)$ ——因为 n 很大时 $n ²$ 那项主导，前面的常数 3 和后面的 5n、100 都被 $n ²$ 淹没了。所以大 O 不是「具体多少秒」，而是「当 n 翻倍，时间会怎么变」的趋势描述： $O (n)$ 的算法 n 翻倍时间也翻倍、 $O (n ²)$ 的算法 n 翻倍时间变 4 倍、 $O (\log n)$ 的算法 n 翻倍时间只多一点点。

为什么忽略常数？因为常数受机器、编译器、缓存影响（同一算法在快机器和慢机器上时间差几倍），但「趋势」是算法本身的属性、跨机器不变。大 O 抓的是这个「跨机器不变的内核」。

常见量级：从快到慢

下面这几个量级覆盖了绝大多数常见算法（从快到慢）：

量级	名字	典型算法/操作	`n` 翻倍时
$O (1)$	常数	哈希表平均查找、栈 push/pop、链表头插	时间不变
$O (\log n)$	对数	二分查找、平衡 BST 操作	时间只增常数
$O (n)$	线性	链表/数组遍历、线性查找	时间翻倍
$O (n \log n)$	线性对数	快排/归并平均、堆排	时间约 ×2 多一点
$O (n ²)$	平方	冒泡/插入/选择、BST 退化	时间 ×4
$O (2 ⁿ)$ / $O (n!)$	指数/阶乘	暴力子集、全排列	直接爆炸

记住这张表「从上到下越来越慢」的顺序，再记住 n 翻倍时各自的反应——这就是大 O 的全部基础。 $O (1)$ 最快（不管 n 多大都恒定时间）、 $O (2 ⁿ)$ 和 $O (n!)$ 是灾难（n 才到三四十就跑不完，本章不展开）。我们前面写的所有算法，都落在 $O (1)$ 到 $O (n ²)$ 这段。

真跑对比一：冒泡 O(n²) vs 快排 O(n log n)

光说「 $O (n ²)$ 比 $O (n \log n)$ 慢」太抽象，真跑一遍最直白。我们用 clock()（§7.27.2，返回程序迄今用的 CPU 时间）给冒泡排序和标准库 qsort（快排）在同一组随机数据上计时，看 n 从 2000 涨到 8000 时两者耗时的变化：

展开代码 (共 62 行)收起代码

/* 用 clock() 给冒泡 O(n²) 和快排 O(n log n) 计时,看量级差距 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void bubble_sort(int* a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swapped = 1;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

static int cmp(const void* a, const void* b) {
    int x = *(const int*)a;
    int y = *(const int*)b;
    return (x > y) - (x < y); /* 防 a-b 异号溢出 */
}

int main(void) {
    for (int n = 2000; n <= 8000; n += 2000) {
        int* a = malloc((size_t)n * sizeof(int));
        int* b = malloc((size_t)n * sizeof(int));
        if (!a || !b) {
            return 1;
        }
        for (int i = 0; i < n; i++) {
            a[i] = rand(); /* 乱序数据,冒泡的 swapped 优化不生效 */
        }

        for (int i = 0; i < n; i++) {
            b[i] = a[i];
        }
        clock_t t1 = clock();
        bubble_sort(b, n);
        clock_t t2 = clock();
        double sec_bubble = (double)(t2 - t1) / CLOCKS_PER_SEC;

        for (int i = 0; i < n; i++) {
            b[i] = a[i];
        }
        t1 = clock();
        qsort(b, (size_t)n, sizeof(int), cmp);
        t2 = clock();
        double sec_quick = (double)(t2 - t1) / CLOCKS_PER_SEC;

        printf("n=%5d: 冒泡 %.4fs  快排 %.4fs  (比值 %.0fx)\n", n, sec_bubble, sec_quick,
               sec_bubble / sec_quick);
        free(a);
        free(b);
    }
    return 0;
}

text

$ gcc -std=c11 -Wall complexity.c -o cx && ./cx
n= 2000: 冒泡 0.0045s  快排 0.0002s  (比值 22x)
n= 4000: 冒泡 0.0178s  快排 0.0004s  (比值 40x)
n= 6000: 冒泡 0.0410s  快排 0.0007s  (比值 58x)
n= 8000: 冒泡 0.0708s  快排 0.0010s  (比值 72x)

把这两组数对照着看。冒泡：n 从 2000 翻倍到 4000，时间从 0.0045s 涨到 0.0178s——翻了 4 倍；再翻倍到 8000，时间 0.0708s——又是 4 倍。这正是 $O (n ²)$ 的招牌：n 翻倍、时间 ×4。快排：n 同样翻倍，时间从 0.0002s 涨到 0.0010s——只长了 5 倍（不是 4×4=16 倍），增长缓慢得多，这是 $O (n \log n)$ 的样子。最震撼的是最后一列「比值」：n=2000 时冒泡只比快排慢 22 倍，可 n 涨到 8000，这个比值飙升到 72 倍——n 越大， $O (n ²)$ 比 $O (n \log n)$ 慢得越离谱。这就是大 O 想告诉你的核心：量级的差距会随 n 放大，小数据看不出来、大数据上就是「秒级」和「毫秒级」的天壤之别。（这些秒数每次跑会因机器负载略变，但「冒泡 n 翻倍时间 ×4」「比值随 n 一路涨」这两个趋势是稳定的——大 O 抓的就是这种不随机器变的趋势。）

真跑对比二：线性 O(n) vs 二分 O(log n)

再看一个更极端的对照——在有序数组里找一个数，线性扫描（从头顺着找， $O (n)$ ）和二分查找（每次砍一半， $O (\log n)$ ，第 11 章）。我们在 100 万元素里查最末那个元素（线性最坏、二分也走到最深），重复 100 次累积计时：

展开代码 (共 65 行)收起代码

/* 线性查找 O(n) vs 二分查找 O(log n):同样在有序数组里查最末元素,重复 K 次计时 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static int linear_search(const int* a, int n, int key) {
    for (int i = 0; i < n; i++) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}

static int binary_search(const int* a, int n, int key) {
    int lo = 0;
    int hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; /* 防 lo+hi 溢出 */
        if (a[mid] == key) {
            return mid;
        }
        if (a[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

int main(void) {
    int n = 1000000;     /* 100 万元素 */
    int reps = 100;      /* 重复 100 次累积(单次太短测不准) */
    int* a = malloc((size_t)n * sizeof(int));
    if (!a) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        a[i] = i;        /* 有序 0..n-1 */
    }
    int key = n - 1;     /* 查最末(线性最坏、二分也走到最深) */

    clock_t t1 = clock();
    int found = -1;
    for (int k = 0; k < reps; k++) {
        found = linear_search(a, n, key);
    }
    clock_t t2 = clock();
    double sec_linear = (double)(t2 - t1) / CLOCKS_PER_SEC;

    t1 = clock();
    for (int k = 0; k < reps; k++) {
        found = binary_search(a, n, key);
    }
    t2 = clock();
    double sec_binary = (double)(t2 - t1) / CLOCKS_PER_SEC;

    printf("n=%d 查 %d(重复 %d 次):\n", n, key, reps);
    printf("  线性 O(n)      : %.6fs  (找到下标 %d)\n", sec_linear, found);
    printf("  二分 O(log n)  : %.6fs  (比值 %.0fx)\n", sec_binary, sec_linear / sec_binary);

    free(a);
    return 0;
}

text

$ gcc -std=c11 -Wall search_compare.c -o sc && ./sc
n=1000000 查 999999(重复 100 次):
  线性 O(n)      : 0.095949s  (找到下标 999999)
  二分 O(log n)  : 0.000008s  (比值 11994x)

差了整整 12000 倍。线性查找 100 万次（重复 100 回合、每回从 0 扫到 999999）花了近 0.1 秒；二分查找每回只比较约 20 次（ $\log ₂ (1000000) \approx 20$ ）、100 回合也就 2000 次比较，快到几乎测不出时间（0.000008s）。这就是 $O (\log n)$ 的恐怖之处：n 涨到 100 万， $\log n$ 才 20——「每次砍一半」让规模按指数级缩水。如果你在一个性能敏感的程序里、对有序数据还用线性扫描，那等于白白浪费了一万倍的性能。这就是为什么第 11 章说「二分的前提是数据有序」——为了能用上 $O (\log n)$ 、值得先花 $O (n \log n)$ 排个序。

前面所有操作，一张大 O 表落位

把阶段 3 前面 11 章写过的所有操作在一张表上落位，你会看到大 O 怎么把「选数据结构」变成一道有标准答案的题：

操作	数据结构/算法	复杂度	出处
头插 / 头删	单链表	$O (1)$	第 1 章
push / pop	栈（数组/链表）	$O (1)$	第 3 章
enqueue / dequeue	队列（环形/链表）	$O (1)$	第 4 章
push（均摊）	动态数组	$O (1)$	第 5 章
按下标访问	动态数组	$O (1)$	第 5 章
按值查找	单链表	$O (n)$	第 1 章
线性查找	有序/无序数组	$O (n)$	第 11 章
插入 / 查找 / 删除（平均）	BST（平衡）	$O (\log n)$	第 7 章
二分查找	有序数组	$O (\log n)$	第 11 章
插入 / 查找 / 删除（平均）	哈希表	$O (1)$	第 8 章
冒泡 / 插入 / 选择	排序	$O (n ²)$	第 9 章
快排 / 归并（平均）	排序	$O (n \log n)$	第 10 章

这张表就是阶段 3 的「地图」。面对一个问题，先想清楚「我要做什么操作、做多少次」，再照这张表选结构：要「按值快速查」、key 分布均匀——哈希表（平均 $O (1)$ ）；要「有序遍历 + 范围查询」——BST（ $O (\log n)$ + 中序有序）；要「后进先出 / 先进先出」——栈 / 队列（ $O (1)$ ）；要「按下标随机访问 + 动态扩容」——动态数组（ $O (1)$ 访问、均摊 $O (1)$ push）。选错的代价，就是上一节那个 12000 倍的差距。

空间复杂度与均摊

大 O 不只描述时间，也描述空间——算法额外占多少内存，随 n 怎么长。比如归并排序要 $O (n)$ 的临时数组（第 10 章）、快排只要 $O (\log n)$ 的递归栈（原地分区）、二分查找 $O (1)$ （迭代版）或 $O (\log n)$ （递归栈）。多数场景时间复杂度更关键、空间是次要约束，但嵌入式或大数据里空间复杂度也成硬指标。

最后说一个容易被忽略的点——均摊（amortized）。动态数组（第 5 章）的 push 大多数时候是 $O (1)$ （直接写 data[size++]），但偶尔满了要 realloc 扩容、那次是 $O (n)$ （拷贝所有旧元素）。单看「最坏」它是 $O (n)$ ，但因为扩容很少发生（容量翻倍、n 次 push 才扩容约 $\log n$ 次），把 $O (n)$ 的那次扩容摊到 n 次 push 上，每次 push 的均摊成本仍是 $O (1)$ 。所以动态数组的 push 说「均摊 $O (1)$ 」比说「最坏 $O (n)$ 」更准确——这正是 C++ std::vector::push_back 的复杂度约定。理解均摊，你才能解释「为什么动态数组明明偶尔要慢一下、整体还是被当成 $O (1)$ 容器用」。

小结

大 O 记号描述算法运行时间/空间随输入规模 n 增长的渐进上界，只看趋势、忽略常数（因为常数受机器影响、趋势是算法本身的不变属性）。常见量级从快到慢： $O (1)$ （哈希表平均、栈 push、链表头插）、 $O (\log n)$ （二分查找、平衡 BST）、 $O (n)$ （遍历、线性查找）、 $O (n \log n)$ （快排/归并平均）、 $O (n ²)$ （冒泡/插入/选择、BST 退化）；n 翻倍时它们分别是「不变 / 增常数 / ×2 / 略超 ×2 / ×4」。真跑用 clock() 给冒泡 $O (n ²)$ 和快排 $O (n \log n)$ 计时:n 从 2000 到 8000,冒泡时间 0.0045→0.0708s(n 翻倍时间 ×4,招牌 $O (n ²)$ )、快排 0.0002→0.0010s(增长缓慢),比值从 22x 一路飙到 72x——量级差距随 n 放大。线性 $O (n)$ vs 二分 $O (\log n)$ 在 100 万元素里查最末:差 12000 倍(线性 0.096s、二分 0.000008s), $\log ₂ (1000000) \approx 20$ 让「每次砍一半」威力惊人。把阶段 3 所有操作落位成一张大 O 表(链表头插 $O (1)$ 、BST 平均 $O (\log n)$ 、哈希平均 $O (1)$ 、冒泡 $O (n ²)$ 、快排 $O (n \log n)$ ),选数据结构就成了一道有标准答案的题——按值快速查用哈希、范围查询用 BST、随机访问用动态数组,选错就是千万倍代价。大 O 也描述空间(归并 $O (n)$ 临时数组、快排 $O (\log n)$ 递归栈)。动态数组 push 大多数 $O (1)$ 、偶尔扩容 $O (n)$ ,均摊下来仍是 $O (1)$ (std::vector::push_back 的约定)。大 O 是阶段 3 的总收口、也是后续系统编程挑数据结构的依据。阶段 3 完结。

参考资源

ISO/IEC 9899:2011 §7.27.1（CLOCKS_PER_SEC）、§7.27.2（clock 函数）、§7.22.5.2（qsort）、bsearch（§7.22.5）
Thomas H. Cormen 等《Introduction to Algorithms》(CLRS) 第 1-3 章(算法复杂度、大 O 记号、增长函数)
Robert Sedgewick《Algorithms in C》第 2 章(算法分析、大 O、时间/空间复杂度)
K. N. King《C Programming: A Modern Approach》第 17 章(排序算法复杂度对照)
阶段3·第 1-11 章(链表/栈/队列/动态数组/树/BST/哈希/排序/查找——本章把它们在一张大 O 表上收口)
阶段 0·第 10 章:标准与优化（-O 优化级别对计时的影响、benchmark 要开 -O2 才反映真实性能）

算法复杂度与大 O：一把尺子量遍前面所有算法 ​

引言：前面 11 章的算法，到底谁快谁慢 ​

大 O 是什么：看趋势，不看常数 ​

常见量级：从快到慢 ​

真跑对比一：冒泡 O(n²) vs 快排 O(n log n) ​

真跑对比二：线性 O(n) vs 二分 O(log n) ​

前面所有操作，一张大 O 表落位 ​

空间复杂度与均摊 ​

小结 ​

参考资源 ​