第一章：算法分析¶

程序 = 数据结构 + 算法。算法分析衡量的是"当输入规模趋近无穷大时，程序表现的变化趋势"。

时间复杂度¶

Big-O 记号¶

\(O(f(N))\) 描述算法运行时间的上界，关注的是当 \(N \to \infty\) 时的增长趋势，忽略常数因子和低阶项。

常见代码结构的复杂度¶

简单循环

1
2
3
4
5
6

for (int i = 0; i < N; i++)    // O(N)
    sum += a[i];

for (int i = 0; i < N; i++)    // O(N²)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

条件语句

1
2
3
4

if (condition)
    fun1();  // O(N)
else
    fun2();  // O(N²)

顺序执行

1
2

for (...) {}   // O(N)
for (...) {}   // O(N²)

1
2
3

for (int i = 1; i <= N; i *= 2)       // O(log N)
    for (int j = 1; j <= i; j++)      // 内层执行 1+2+4+...+N ≈ 2N
        count++;

递归算法分析¶

主定理 (Master Theorem)¶

对形如 \(T(N) = a \cdot T(N/b) + f(N)\) 的递推式（\(a\ge 1, b>1\)）：

典型例子

数学归纳法¶

用于证明递推式的解或算法性质。

三步走： 1. Base Case：证明 \(N\) 取初值时命题成立 2. 归纳假设：假设对所有 \(k < N\) 命题成立 3. 归纳步：利用假设证明 \(N\) 时命题成立

例题：证明 \(T(N) = T(N-1) + 1\)（\(T(1)=1\)）的解为 \(T(N)=N\)。

• Base：\(T(1)=1\)，成立
• 假设 \(T(N-1) = N-1\)
• 则 \(T(N) = T(N-1) + 1 = (N-1) + 1 = N\)

例题：证明 \(T(N) = 2T(N/2) + N\) 的解为 \(T(N) = N\log N + N\)（\(N\) 为 2 的幂）。

• Base：\(N=1\) 时 \(T(1)=1\)，\(1\cdot\log 1+1=1\)，成立
• 假设 \(T(N/2) = \frac{N}{2}\log\frac{N}{2} + \frac{N}{2}\)
• 则 \(T(N) = 2\left(\frac{N}{2}\log\frac{N}{2} + \frac{N}{2}\right) + N = N(\log N - 1) + N + N = N\log N + N\)

空间复杂度¶

衡量算法执行所需的额外存储空间（不含输入数据本身）。

• 原地算法 (In-place)：仅需 \(O(1)\) 额外空间（如插入排序、堆排序）
• 非原地算法：需要额外数组/递归栈（如归并排序需 \(O(N)\)）

复杂度速查¶