算法分析

这一页整理 Ch02 Algorithm Analysis。重点是算法定义、时间/空间复杂度、渐进符号、循环与分支分析、二分查找、最大子列和、递归式、主定理和递归 Fibonacci。

1. 算法是什么

算法（algorithm）是一组有限的指令。
如果按照这些指令执行，就能完成某个特定任务。

一个算法必须满足五个条件：

条件	含义
Input	有零个或多个外部输入
Output	至少产生一个输出
Definiteness	每条指令清楚、无歧义
Finiteness	对所有情况，有限步后终止
Effectiveness	每一步足够基本，原则上能用纸笔执行

注意：程序不一定等于算法。
程序是用某种编程语言写出来的实现，而算法可以用自然语言、流程图、伪代码或程序语言描述。

例如操作系统程序可以一直运行，不一定满足 finiteness；但算法必须在有限步内结束。

2. 分析什么

算法分析不关心某台机器、某个编译器下跑了多少秒。
这些运行时间会受硬件、编译器、系统状态影响，不够稳定。

我们更关心的是：

时间复杂度 time complexity
空间复杂度 space complexity

它们描述的是输入规模变大时，算法消耗的时间和空间如何增长。

课件中常用的简化假设：

• 指令按顺序执行。
• 每条简单指令花费一个时间单位。
• 整数大小固定。
• 有足够的内存。

通常会分析两个函数：

Tavg(N)    平均时间复杂度
Tworst(N) 最坏时间复杂度

如果输入规模不止一个变量，就不要强行合成一个 N。
例如矩阵加法要写成 T(rows, cols)。

3. 为什么不执着精确步数

课件给过求和函数的例子。

迭代求和：

float sum(float list[], int n) {
    float tempsum = 0;
    for (int i = 0; i < n; i++) {
        tempsum += list[i];
    }
    return tempsum;
}

精确数步可以得到类似：

Tsum(n) = 2n + 3

递归求和：

float rsum(float list[], int n) {
    if (n) {
        return rsum(list, n - 1) + list[n - 1];
    }
    return 0;
}

精确数步可能得到：

Trsum(n) = 2n + 2

但这不代表递归版本一定更快。
因为递归调用本身还有额外开销，而且精确数步非常依赖计数模型。

所以算法分析真正关心的是增长趋势：

2n + 3 和 2n + 2 都是 Θ(N)

这就是为什么要用渐进符号，而不是死抠每一条语句到底算几步。

4. 渐进符号

设 T(N) 是程序运行时间，f(N) 是一个简单函数。

符号	含义	直觉
O(f(N))	上界	f(N) 是T的上界
Ω(f(N))	下界	f(N) 是 T 的下界
Θ(f(N))	紧确界	和 f(N) 同阶
o(f(N))	严格低阶	T比 f(N) 慢

5. 常见复杂度增长

从慢到快大致是：

1 < log N < N < N log N < N^2 < N^3 < 2^N < N!

• 指数和阶乘增长很快，N 稍大就不可接受。
• log N 增长非常慢，所以二分、堆、平衡树这类带 log 的算法通常很高效。

6. 复杂度运算法则

连续语句

连续执行的代码，复杂度相加，最后取增长最快的那一项：

O(N) + O(N^2) = O(N^2)

for 循环

循环复杂度约等于：

循环次数 × 循环体复杂度

例如：

for (int i = 0; i < n; i++) {
    sum += a[i];
}

循环 n 次，每次 O(1)，所以总复杂度是：

O(N)

嵌套循环

嵌套循环通常把每层循环次数相乘：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        x++;
    }
}

总共执行 N × N 次：

O(N^2)

但不是所有双层循环都是 O(N^2)，要看真实执行次数。
尤其要小心这两类情况：

• 某一层循环不是跑 N 次，而是 log N 次。
• 循环上界不是 N，而是 N^2、N^3 或和外层变量有关。

例如下面这个双层循环就是 O(N log N)，不是 O(N^2)：

for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < n; j++) {
        x++;
    }
}

外层 i 每次翻倍：

1, 2, 4, 8, ..., N

所以外层是 O(log N) 次，内层每次 O(N)，总复杂度是：

O(N log N)

例题：分支与多层循环

if (A > B) {
    for (i = 0; i < N * 2; i++)
        for (j = N * N; j > i; j--)
            C += A;
} else {
    for (i = 0; i < N * N / 100; i++)
        for (j = N; j > i; j--)
            for (k = 0; k < N * 3; k++)
                C += B;
}

问：最低的上界（lowest upper bound）是多少？

点拨：if 分支是 O(N) × O(N^2) = O(N^3)。else 分支里，虽然外层写到 N^2/100，但当 i >= N 时中间层 j > i 不成立，所以真正有贡献的只有前 N 轮；中间层总次数是 Θ(N^2)，再乘最内层 O(N)，也是 O(N^3)。

答案：

O(N^3)

if / else

条件分支取较大的分支：

O(test) + max(O(S1), O(S2))

例如：

if (x > 0) {
    do_O_N_work();
} else {
    do_O_N2_work();
}

最坏情况是：

O(N^2)

7. 矩阵加法例子

课件里的矩阵加法：

void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE],
         int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            c[i][j] = a[i][j] + b[i][j];
        }
    }
}

外层循环 rows 次，内层循环 cols 次。
因此：

T(rows, cols) = Θ(rows × cols)

注意输入规模有两个变量时，不要强行只写 N。
如果题目明确 rows = cols = N，才可以写成 Θ(N^2)。

8. 二分查找与对数复杂度

二分查找要求数组已经有序：

A[0] <= A[1] <= ... <= A[N - 1]

每次比较中间元素 A[mid]：

• 如果 A[mid] == X，找到。
• 如果 A[mid] < X，只需要查右半边。
• 如果 A[mid] > X，只需要查左半边。

可视化：

原区间: [0............................N-1]
第1次:  [0............mid............N-1]   丢掉一半
第2次:                  [mid+1......N-1]   再丢掉一半
第3次:                         [....]      继续减半

每次规模除以 2：

N -> N/2 -> N/4 -> N/8 -> ... -> 1

假设做了 k 次以后规模变成 1：

N / 2^k = 1

所以：

2^k = N
k = log2 N

因此二分查找最坏复杂度是：

O(log N)

课件中的代码可以写成：

int BinarySearch(const ElementType A[], ElementType X, int N) {
    int Low, Mid, High;

    Low = 0;
    High = N - 1;

    while (Low <= High) {
        Mid = (Low + High) / 2;

        if (A[Mid] < X) {
            Low = Mid + 1;
        } else if (A[Mid] > X) {
            High = Mid - 1;
        } else {
            return Mid;
        }
    }

    return -1;
}

更稳一点的写法是：

Mid = Low + (High - Low) / 2;

这样可以避免 Low + High 在极大数组下溢出。

9. 前缀和

前缀和是这章里最值得补充的技巧之一。
它的作用是把“反复求区间和”从每次 O(N) 降到每次 O(1)。

给定数组：

A = [4, -3, 5, -2, -1, 2, 6, -2]

定义前缀和数组 S：

S[0] = 0
S[i + 1] = S[i] + A[i]

可视化如下：

下标 i:    0    1    2    3    4    5    6    7
A[i]:      4   -3    5   -2   -1    2    6   -2

S下标:     0    1    2    3    4    5    6    7    8
S[i]:      0    4    1    6    4    3    5   11    9

区间 [i, j] 的和为：

A[i] + A[i+1] + ... + A[j] = S[j + 1] - S[i]

例如求 A[2..6]：

A[2..6] = 5 + (-2) + (-1) + 2 + 6 = 10
S[7] - S[2] = 11 - 1 = 10

为什么前缀和能相减

S[j+1] 表示从 A[0] 加到 A[j]。
S[i] 表示从 A[0] 加到 A[i-1]。

两者相减，前面公共部分被抵消，剩下的正好是 A[i] 到 A[j]：

S[j+1] = A[0] + A[1] + ... + A[i-1] + A[i] + ... + A[j]
S[i]   = A[0] + A[1] + ... + A[i-1]
-----------------------------------------------
差值   = A[i] + ... + A[j]

前缀和代码

int prefix[MAXN + 1];

prefix[0] = 0;
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + A[i];
}

int rangeSum(int l, int r) {
    return prefix[r + 1] - prefix[l];
}

预处理：

O(N)

每次查询：

O(1)

10. 最大子列和

题目：给定整数序列 A1, A2, ..., AN，允许负数，求连续子列的最大和。
课件约定：如果所有数都是负数，最大和为 0，即允许选择空子列。

例子：

A = [4, -3, 5, -2, -1, 2, 6, -2]

最大子列是：

[4, -3, 5, -2, -1, 2, 6]

和为：

11

算法 1：三重循环

枚举起点 i、终点 j，再用 k 从 i 加到 j。

枚举 i: O(N)
枚举 j: O(N)
求 A[i..j]: O(N)
总复杂度: O(N^3)

这是最直接但最慢的方法。

算法 2：边枚举边累加

固定起点 i 后，让 j 向右移动，并维护当前和 ThisSum：

MaxSum = 0;
for (int i = 0; i < N; i++) {
    ThisSum = 0;
    for (int j = i; j < N; j++) {
        ThisSum += A[j];
        if (ThisSum > MaxSum) {
            MaxSum = ThisSum;
        }
    }
}

这样不需要每次重新从 i 加到 j，总复杂度降为：

O(N^2)

前缀和版本的 O(N^2)

前缀和也能把任意区间和变成 O(1)：

MaxSum = 0;
for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
        ThisSum = prefix[j + 1] - prefix[i];
        if (ThisSum > MaxSum) {
            MaxSum = ThisSum;
        }
    }
}

复杂度仍是：

O(N^2)

因为区间个数本身就是 N(N+1)/2 个。
但前缀和让“求每个区间和”这件事变得更清楚，也更容易迁移到其他区间和题目。

算法 3：分治

把数组从中间分成左右两半。最大子列和只有三种可能：

1. 完全在左半边
2. 完全在右半边
3. 跨过中线

可视化：

[ 左半边 ........ ][ ........ 右半边 ]
       情况1              情况2
              [跨过中线的情况3]

左半边和右半边递归求。
跨过中线的最大和可以在线性时间内求：

• 从中线向左扫，找最大左边界和。
• 从中线向右扫，找最大右边界和。
• 两者相加。

递归式：

T(N) = 2T(N/2) + O(N)

由主定理可得：

T(N) = O(N log N)

算法 4：在线算法 / Kadane

课件中的 On-line Algorithm 只扫描一遍数组：

int MaxSubsequenceSum(const int A[], int N) {
    int ThisSum, MaxSum, j;

    ThisSum = MaxSum = 0;
    for (j = 0; j < N; j++) {
        ThisSum += A[j];

        if (ThisSum > MaxSum) {
            MaxSum = ThisSum;
        } else if (ThisSum < 0) {
            ThisSum = 0;
        }
    }

    return MaxSum;
}

核心思想：

• ThisSum 表示“以当前扫描位置结尾，还值得继续保留的子列和”。
• 如果 ThisSum < 0，说明前面这一段只会拖累后面的结果，直接丢掉，从下一位重新开始。
• MaxSum 记录历史上见过的最大子列和。

可视化：

A:        4   -3    5   -2   -1    2    6   -2
ThisSum:  4    1    6    4    3    5   11    9
MaxSum:   4    4    6    6    6    6   11   11

复杂度：

O(N)

这是最大子列和最重要的版本。

四种算法对比

方法	思路	复杂度	重点
算法 1	枚举 i,j,k	O(N^3)	会分析三重循环
算法 2	固定 i，累加到 j	O(N^2)	避免重复求和
前缀和版	S[j+1] - S[i]	O(N^2)	区间和 O(1)
算法 3	分治	O(N log N)	递归式和主定理
算法 4	在线算法	O(N)	扫一遍，负和归零

11. 主定理

主定理用于快速求解这类递归式：

T(N) = aT(N/b) + f(N)

含义：

• a：每次分成几个子问题。
• N/b：每个子问题的规模。
• f(N)：分解、合并、额外处理的代价。

关键是比较：

f(N)  和  N^(log_b a)

其中 N^(log_b a) 可以理解成递归树叶子层的总规模。

12. 主定理三种情况

令：

p = log_b a

比较 f(N) 和 N^p。

例题：两个递归式比较

已知：

P1: T(1) = 1, T(N) = T(N/3) + 1
P2: T(1) = 1, T(N) = 3T(N/3) + 1

问：两者的复杂度分别是多少？

点拨：P1 每次只剩一个 N/3 子问题，递归深度是 log_3 N。P2 套主定理，a = 3, b = 3，所以 N^(log_b a) = N，而 f(N)=1，属于 Case 1。

答案：

P1: O(log N)
P2: O(N)

Case 1：子问题主导

如果：

f(N) = O(N^(p - ε))

也就是 f(N) 比 N^p 小一个多项式量级，那么：

T(N) = Θ(N^p)

例子：

T(N) = 2T(N/2) + 1

这里：

a = 2, b = 2, p = log_2 2 = 1
f(N) = 1

1 比 N 小，所以：

T(N) = Θ(N)

Case 2：每层一样重

如果：

f(N) = Θ(N^p log^k N)

那么：

T(N) = Θ(N^p log^(k+1) N)

最常见的是 k = 0：

f(N) = Θ(N^p)
T(N) = Θ(N^p log N)

例子：最大子列和分治、归并排序。

T(N) = 2T(N/2) + N

这里：

a = 2, b = 2, p = 1
f(N) = N = Θ(N^p)

所以：

T(N) = Θ(N log N)

Case 3：合并代价主导

如果：

f(N) = Ω(N^(p + ε))

并且满足正则条件：

a f(N/b) <= c f(N), 其中 c < 1

那么：

T(N) = Θ(f(N))

例子：

T(N) = 2T(N/2) + N^2

这里：

p = log_2 2 = 1
f(N) = N^2

N^2 比 N 大一个多项式量级，所以：

T(N) = Θ(N^2)

13. 主定理可视化：递归树

以：

T(N) = 2T(N/2) + N

为例。

每层的额外代价都是 N：

第0层:              N
                 /     \
第1层:          N/2     N/2          总和 N
              /   \    /   \
第2层:       N/4 N/4 N/4 N/4        总和 N

...

一共 log N 层

所以总复杂度是：

N + N + ... + N = N log N

这就是主定理 Case 2 的直觉：每一层都差不多重，层数是 log N。

再看：

T(N) = 2T(N/2) + N^2

每层代价：

第0层: N^2
第1层: 2 × (N/2)^2 = N^2/2
第2层: 4 × (N/4)^2 = N^2/4
...

越往下越小，总和被第一层主导：

T(N) = Θ(N^2)

14. 常见递归式速查

递归式	结果	说明
T(N) = T(N/2) + O(1)	O(log N)	二分查找
T(N) = T(N/2) + O(N)	O(N)	每层总代价递减
T(N) = 2T(N/2) + O(1)	O(N)	子问题主导
T(N) = 2T(N/2) + O(N)	O(N log N)	归并排序、分治最大子列和
T(N) = 2T(N/2) + O(N^2)	O(N^2)	合并代价主导
T(N) = 3T(N/2) + O(N)	O(N^{log_2 3})	子问题更多

15. 递归 Fibonacci 为什么很慢

课件里的递归 Fibonacci：

long int Fib(int N) {
    if (N <= 1) {
        return 1;
    } else {
        return Fib(N - 1) + Fib(N - 2);
    }
}

递归式：

T(N) = T(N - 1) + T(N - 2) + O(1)

这不是主定理形式，因为子问题规模不是 N/b，而是 N-1 和 N-2。
它会产生大量重复计算，复杂度指数级增长。

时间复杂度证明

先忽略常数项，只看增长趋势。递归 Fibonacci 的时间满足：

T(N) = T(N - 1) + T(N - 2) + O(1)

它和 Fibonacci 数列本身非常像：

F(N) = F(N - 1) + F(N - 2)

所以可以把 T(N) 理解成“至少像 Fibonacci 数列一样增长”。

下界：

T(N) >= T(N - 1) + T(N - 2)

因此：

T(N) = Ω(F(N))

而 Fibonacci 数列是指数级增长，常用近似是：

F(N) ≈ φ^N / sqrt(5)

其中：

φ = (1 + sqrt(5)) / 2 ≈ 1.618

所以递归 Fibonacci 的时间至少是：

Ω(φ^N)

上界也可以粗略估计。因为：

T(N - 2) <= T(N - 1)

所以：

T(N) = T(N - 1) + T(N - 2) + O(1)
     <= 2T(N - 1) + O(1)

不断展开可得：

T(N) = O(2^N)

因此，朴素递归 Fibonacci 的时间复杂度可以写成：

T(N) = Ω(φ^N), 且 T(N) = O(2^N)

在数据结构课里通常把它概括为：

指数级时间复杂度

如果要写得更贴近精确增长，可以记成：

T(N) = Θ(F(N)) = Θ(φ^N)

可视化：

Fib(5)
├─ Fib(4)
│  ├─ Fib(3)
│  │  ├─ Fib(2)
│  │  └─ Fib(1)
│  └─ Fib(2)
└─ Fib(3)
   ├─ Fib(2)
   └─ Fib(1)

Fib(3)、Fib(2) 被重复计算很多次，所以它很慢。

例题：递归 Fibonacci 的空间复杂度

递归计算：

F0 = 0, F1 = 1, FN = F(N-1) + F(N-2)

问：递归函数计算 FN 的空间复杂度是多少？

点拨：问的是空间，不是时间。递归树很大，但同一时刻主要占用的是调用栈；最长调用链是 Fib(N) -> Fib(N-1) -> ... -> Fib(1)，深度为 N。

答案：

O(N)

16. 检查复杂度分析

课件给了两个检查方法。

方法一：倍增测试

如果：

T(N) = O(N)

那么输入翻倍后，时间大约翻 2 倍：

T(2N) / T(N) ≈ 2

如果：

T(N) = O(N^2)

则：

T(2N) / T(N) ≈ 4

如果：

T(N) = O(N^3)

则：

T(2N) / T(N) ≈ 8

方法二：极限检查

如果猜测：

T(N) = O(f(N))

可以看：

lim T(N) / f(N)

如果极限趋向一个非零常数，通常说明：

T(N) = Θ(f(N))

17. 考点速记

考点	必会内容
渐进符号	O 上界，Ω 下界，Θ 同阶
循环分析	单层看次数，嵌套看总执行次数
矩阵加法	Θ(rows × cols)
二分查找	每次减半，O(log N)
前缀和	S[j+1] - S[i] 求区间和
最大子列和	O(N^3), O(N^2), O(N log N), O(N) 四版对比
在线算法	ThisSum < 0 就归零
主定理	比较 f(N) 和 N^(log_b a)
Fibonacci	递归树重复计算，指数级
倍增测试	O(N^k) 翻倍约变 2^k 倍

18. 易错点

• 不要把 O 当作精确等号，O 只是上界。
• 写复杂度时通常取最紧的简单形式，例如 2N + 3 写 Θ(N)。
• 双层循环不一定都是 N^2，要算真实次数。
• 有多个输入规模时保留多个变量，例如 rows 和 cols。
• 前缀和数组通常多开一位，令 S[0] = 0。
• 区间 [l, r] 的和是 S[r+1] - S[l]，右端点容易写错。
• 主定理只适用于 T(N) = aT(N/b) + f(N) 这种形式。
• T(N) = T(N-1) + T(N-2) + O(1) 不能直接套主定理。