第 1 章 · 复杂度分析

复杂度分析回答：n 变大时程序要花多少时间、多少内存，只看增长趋势，不依赖具体机器。

1.1 大 O 记号：只看增长趋势

大 O 描述上界：存在常数 c、n0，使 n ≥ n0 时 T(n) ≤ c·f(n)，则 T(n) = O(f(n))。丢掉常数和低阶项，只留主导项。

// 基本操作次数 T(n) = 2n + 3，记作 O(n)
int sum(int *a, int n) {
    int s = 0;                    // 1
    for (int i = 0; i < n; i++)   // n 次循环
        s += a[i];                // 每次 1 次加法 + 1 次取址
    return s;                     // 1
}

1.2 时间复杂度 vs 空间复杂度

• 时间复杂度：随 n 增长，基本操作次数的增长阶。
• 空间复杂度：除输入本身外，额外占用的内存（辅助空间）增长阶。排序里的「原地（in-place）」就是 O(1) 额外空间。

int max(int *a, int n) {          // 时间 O(n)、额外空间 O(1)
    int m = a[0];
    for (int i = 1; i < n; i++) if (a[i] > m) m = a[i];
    return m;
}
// 归并排序：时间 O(n log n)，但需 O(n) 辅助数组——空间换时间

1.3 最好 / 平均 / 最坏

同一个算法，不同输入表现不同：

情形	含义	顺序查找的例子
最好	最有利输入	目标在第一个位置，O(1)
最坏	最不利输入	目标不存在，O(n)
平均	所有输入等概率	约 n/2 次，O(n)

工程最关心最坏（性能下限保证）；平均需概率假设，较难算（如快排平均 O(n log n)）。

1.4 常见复杂度阶

阶	名称	n=10⁶ 时量级	典型例子
O(1)	常数	1	数组下标访问、哈希查表
O(log n)	对数	~20	二分查找、平衡树
O(n)	线性	10⁶	一趟遍历
O(n log n)	线性对数	~2×10⁷	快排、归并、堆排
O(n²)	平方	10¹²	冒泡、双重循环
O(2ⁿ)	指数	不可行	穷举子集、朴素递归

增长率：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)。n 翻倍，O(n²) 慢 4 倍，O(2ⁿ) 直接爆炸。

// O(n^2)：两层嵌套，n 翻倍 → 时间翻 4 倍
int pairs(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;
}

对比：哈希表用桶换 O(1) 查找（空间换时间）；原地排序省辅助数组（时间换空间）。

1.5 与 C 的联系

复杂度数操作次数，C 能精确数清：一次 *p 解引用 = 一次内存访问，一次 malloc = 一块堆内存（见 C 指针第 1 章）。