Chapter 2: Algorithm Analysis

§0 Algorithm 的定义

【定义】 An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. All algorithms must satisfy:

1. Input — Zero or more quantities are externally supplied.
2. Output — At least one quantity is produced.
3. Definiteness — Each instruction is clear and unambiguous.
4. Finiteness — The algorithm terminates after a finite number of steps for all cases.
5. Effectiveness — Every instruction must be basic enough to be carried out by a person using only pencil and paper; each operation must also be feasible.

注：Program 不必须是 finite 的（如操作系统），但 algorithm 必须。
Algorithm 可以用自然语言、流程图、伪代码或编程语言描述。

〖Example〗Selection Sort（伪代码）：

for ( i = 0; i < n; i++) {
    Examine list[i] to list[n−1], find the smallest at list[min];
    Interchange list[i] and list[min];
}

---

§1 What to Analyze（分析什么）

分析目标是 时间复杂度 和 空间复杂度，与机器和编译器无关。

假设：

• 指令顺序执行
• 每条指令只需 1 个时间单位
• 整数大小固定，内存无限

主要分析两个函数：

• $T_{avg}(N)$：平均情况时间复杂度
• $T_{worst}(N)$：最坏情况时间复杂度

〖Example〗矩阵加法：

for (i = 0; i < rows; i++)        /* rows + 1 次 */
    for (j = 0; j < cols; j++)    /* rows*(cols+1) 次 */
        C[i][j] = A[i][j] + B[i][j]; /* rows*cols 次 */

$$T(\text{rows},\text{cols})=2\cdot \text{rows}\cdot \text{cols}+2\text{rows}+1$$

若 rows >> cols，则应交换循环顺序以利用缓存局部性。

〖Example〗迭代求和：

float sum(float list[], int n) {
    float tempsum = 0;          /* count = 1 */
    for (int i = 0; i < n; i++)
        tempsum += list[i];     /* count++ per iteration */
    return tempsum;             /* count++ */
}

$$T_{sum}(n)=2n+3$$

〖Example〗递归求和：

$$T_{rsum}(n)=2n+2$$

两者渐进阶相同，但递归版每步计算开销更大（函数调用栈）。精确计数的意义：有时"小"的常数差异在大 $n$ 下无关紧要，重要的是增长阶。

---

§2 Asymptotic Notation（渐进符号）

Big-O（上界）

【定义】 $T(N)=O(f(N))$ if there exist positive constants $c$ and $n_0$ such that

$$T(N)\le c\cdot f(N)\mathrm{\forall }N\ge n_0$$

即 $f(N)$ 是 $T(N)$ 的上界（asymptotic upper bound）。

Ω（下界）

【定义】 $T(N)=\mathrm{\Omega }(g(N))$ if there exist positive constants $c$ and $n_0$ such that

$$T(N)\ge c\cdot g(N)\mathrm{\forall }N\ge n_0$$

Θ（紧确界）

【定义】 $T(N)=\mathrm{\Theta }(h(N))$ iff $T(N)=O(h(N))$ and $T(N)=\mathrm{\Omega }(h(N))$.

o（严格上界）

【定义】 $T(N)=o(p(N))$ if $T(N)=O(p(N))$ and $T(N)\ne \mathrm{\Omega }(p(N))$.

重要规则

• $2N+3=O(N)=O(N^2)=O(2^N)=\dots$ → 取最小的 $f(N)$
• $2N+N^2=\mathrm{\Omega }(2N)=\mathrm{\Omega }(N^2)=\mathrm{\Omega }(N)=\mathrm{\Omega }(1)=\dots$ → 取最大的 $g(N)$

运算规则

若 $T_1(N)=O(f(N))$，$T_2(N)=O(g(N))$，则：

• $T_1(N)+T_2(N)=max(O(f(N)),O(g(N)))$
• $T_1(N)\cdot T_2(N)=O(f(N)\cdot g(N))$

若 $T(N)$ 是 $k$ 次多项式，则 $T(N)=\mathrm{\Theta }(N^k)$。

${\log }^{k}N=O(N)$ 对任意常数 $k$ 成立（对数增长极慢）。

注意：比较两个程序的渐进复杂度时，必须在 $N$ 充分大的情况下才有意义。例如 $T_{p1}(N)={10}^{6}N$，$T_{p2}(N)=N^2$，当 $N<{10}^6$ 时 $P_2$ 反而更快。

常见复杂度增长排序

$$O(1)<O(\log N)<O(N)<O(N\log N)<O(N^2)<O(N^3)<O(2^N)<O(N!)$$

代码分析规则

结构	时间复杂度
for 循环	循环体时间 × 迭代次数
嵌套 for 循环	循环体时间 × 所有循环大小之积
顺序语句	各语句时间相加（取最大项）
if/else	max(S1 时间, S2 时间) + 条件判断时间
递归	建立并求解递推关系

〖Example〗矩阵加法（渐进版）：

$$T(\text{rows},\text{cols})=\mathrm{\Theta }(\text{rows}\cdot \text{cols})$$

〖Example〗Fibonacci 递归：

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

递推关系：$T(N)=T(N-1)+T(N-2)+2$

由归纳法证明：$T(N)\ge \text{Fib}(N)$，而 $\text{Fib}(N)\approx \frac{{\varphi }^N}{\sqrt{5}}$（$\varphi \approx 1.618$），故 $T(N)=O(2^N)$。

指数级增长，极慢 — 原因是大量重复计算（可用 DP 改进至 $O(N)$）。

---

§3 Compare the Algorithms（最大子序列和问题）

问题： 给定整数序列 $A[0..N-1]$，求最大子序列和。若所有整数为负，答案为 0。

Algorithm 1：$O(N^3)$

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

穷举所有子序列，每对 $(i,j)$ 重新求和。

Algorithm 2：$O(N^2)$

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

固定起点 $i$，逐步扩展 $j$，利用前一步结果，避免内层 $k$ 循环。

Algorithm 3：$O(N\log N)$，分治法

将数组分为左右两半：

• 最大子序列要么完全在左半，要么完全在右半，要么跨越中点。
• 跨中点的情况：从中点向左的最大后缀 + 从中点向右的最大前缀，扫描一遍 $O(N)$。

递推关系：

$$T(N)=2T(N/2)+cN,T(1)=O(1)$$

展开：

$$=2^{k}O(1)+ckN\text{where }N/2^k=1$$$$=O(N\log N)$$

Algorithm 4：$O(N)$，在线算法（Online 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;
}

关键思路： 若当前累积和变为负数，则抛弃它重新从 0 开始——以负数开头的子序列不可能是最大子序列的一部分。

在线（On-line）特性： 算法在任何时间点都能对已读入的数据给出正确答案，不需要提前知道所有输入。数组只扫描一次。

---

§4 Logarithms in the Running Time（对数型时间复杂度）

Binary Search（二分查找）

问题： 在已排序数组 $A[0]\le A[1]\le \dots \le A[N-1]$ 中查找 $X$。

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; /* Found */
    }
    return NotFound; /* -1 */
}

$$T_{worst}(N)=O(\log N)$$

适用场景：数据静态且已排好序（如字典查词）。

请自学：Euclid's Algorithm（欧几里得算法求 GCD）和 Exponentiation（快速幂）。

---

§5 Checking Your Analysis（验证分析）

实验验证渐进复杂度的技巧——统计 $T(2N)/T(N)$ 的比值：

复杂度	期望比值
$O(N)$	$\approx 2$
$O(N^2)$	$\approx 4$
$O(N^3)$	$\approx 8$
$O(N\log N)$	$\approx 2$ (稍大于 $O(N)$)

若实测比值与期望差距较大，说明分析有误或存在隐藏因素。