#绪论与复杂度分析

#考点定位

• 所属大纲章节：绪论（时间复杂度与空间复杂度分析）
• 常见题型：选择题（给定代码片段判断复杂度、给定递推式判断复杂度量级、复杂度大小比较）
• 考查频率：高。复杂度分析本身几乎每年以 1-2 道选择题出现，且是所有算法设计大题的必答项（最后一问"分析算法时间复杂度"白送分或白丢分）

工程直觉迁移：你每天都在做复杂度判断，这部分真正的增量只有两块——渐进符号的数学定义（选择题会抠字眼）和递推式的系统解法（主方法）。

#基本概念：数据结构、算法与复杂度的严格定义

选择题会直接考分类，定义先行：

两条选择题级推论：逻辑结构独立于存储结构——同一线性结构可用顺序或链式两种存储实现（见 02-线性表）；算法与程序的区别在有穷性——操作系统是无限循环的程序，不是算法。

#渐进符号的数学表述

选择题最爱考定义的精确性，尤其是量词方向。设 $f(n)$、$g(n)$ 定义在正整数上：

$O(f) = \{ g(n) \mid \exists\, c > 0,\ \exists\, n_0,\ \forall\, n \ge n_0:\ 0 \le g(n) \le c \cdot f(n) \}$

$O$ 是上界（渐进小于等于），$\Omega$ 是下界，$\Theta$ 是紧确界（同时满足两者）：

$\Omega(f) = \{ g(n) \mid \exists\, c > 0,\ \exists\, n_0,\ \forall\, n \ge n_0:\ g(n) \ge c \cdot f(n) \ge 0 \}$

$\Theta(f) = \{ g(n) \mid \exists\, c_1, c_2 > 0,\ \exists\, n_0,\ \forall\, n \ge n_0:\ c_1 f(n) \le g(n) \le c_2 f(n) \}$

考试抠字眼的方式：

#复杂度计算的选择题考法

#考法一：循环计数

不要模拟执行，数最内层语句的执行次数关于 $n$ 的表达式：

int i = 1;
while (i <= n)
    i = i * 2;   // 执行次数 = floor(log2 n) + 1，复杂度 O(log n)

for (i = 1; i <= n; i++)        // i = 1..n
    for (j = 1; j <= i; j++)    // 内层共 1+2+...+n = n(n+1)/2
        x++;                    // O(n^2)

变式：内层是 for (j = 1; j < 2*i; j++)、双重循环一个乘 2 一个减 1、三层嵌套——统统归约为"内层次数求和"。

#考法二：递推展开

形如"每次规模减半再做 $O(1)$ 工作"：$T(n) = T(n/2) + c \Rightarrow T(n) = O(\log n)$（这就是二分查找，也是选择题常客）。

补：二分查找（折半查找）指在有序顺序表中，每轮将待查值与当前区间的中间元素比较，相等则成功，否则按大小关系舍弃一半区间、在另一半继续——每轮区间规模减半，全站后续章节引用"折半查找"均指此算法。

#考法三：主方法（Master Method）

408 大纲未显式列主方法，但递归复杂度选择题用它秒杀。对

$T(n) = a\,T(n/b) + f(n), \quad a \ge 1,\ b > 1$

记 $n^{\log_b a}$，与 $f(n)$ 比较：

速用实例：

• 归并排序 $T(n) = 2T(n/2) + O(n)$：$\log_2 2 = 1$，$f(n)=n$ 与 $n^1$ 同阶 → $O(n\log n)$
• 二分查找 $T(n) = T(n/2) + O(1)$：$n^{\log_2 1} = 1$，$f=1$ 同阶 → $O(\log n)$
• 快速排序最好情况 $T(n)=2T(n/2)+O(n)$ → $O(n\log n)$；最坏 $T(n)=T(n-1)+O(n)$ 不满足主方法形式（$b=1$ 不允许），直接展开为 $\sum i = O(n^2)$

坑：$T(n) = 2T(n/2) + n\log n$ 落在情形 2 与 3 之间的缝隙，结论是 $O(n\log^2 n)$——408 选择题基本不碰这种边角，遇到先检查是不是自己把递推式列错了。

#例题（模拟题）

例 1：以下代码片段的时间复杂度为（ ）

int count = 0;
for (i = 1; i <= n; i *= 2)
    for (j = 1; j <= n; j++)
        count++;

A. $O(n)$ B. $O(n\log n)$ C. $O(n^2)$ D. $O(\log n)$

解答：外层执行 $O(\log n)$ 次，每次内层 $O(n)$，相乘得 $O(n\log n)$，选 B。错因提醒：把外层次数看成 $n$。

例 2：$T(n) = 4T(n/2) + n$ 的渐进时间复杂度为（ ）

A. $O(n)$ B. $O(n\log n)$ C. $O(n^2)$ D. $O(n^2\log n)$

解答：$n^{\log_2 4} = n^2$，$f(n)=n = O(n^{2-\epsilon})$，情形 1，$T(n)=\Theta(n^2)$，选 C。

#常见坑

1. 加法与乘法规则：顺序执行取 max，嵌套执行取乘积。选择题会给出"并列两段循环，一段 $O(n^2)$ 一段 $O(n\log n)$"问总复杂度，答案是 $O(n^2)$。
2. $\log$ 的底数无关性：$\log_a n = \log_b n / \log_b a$，底数只差常数因子，复杂度里一律写 $\log n$。
3. 递归调用的空间复杂度：栈深度等于递归深度，不是调用总次数。$n!$ 递归空间 $O(n)$；二分查找递归空间 $O(\log n)$。
4. 最好/最坏/平均：题目没说明时，默认问最坏时间复杂度；题干明确问"平均"时注意等概率假设（如顺序表插入平均移动 $n/2$ 次）。

#自测

1. 用 $O/\Omega/\Theta$ 定义说明：$2n^2 + 3n\log n = \Theta(n^2)$ 是否成立？给出常数。
2. for (i=0; i<n; i++) for (j=i; j<n; j++) x++; 的复杂度？
3. $T(n) = 3T(n/4) + n\log n$ 的复杂度量级？（提示：$n^{\log_4 3} \approx n^{0.79}$）
4. 递归计算斐波那契数列 fib(n)（两次自调用）的时间复杂度是多少？为什么？

答案与简析

1. 成立。取 $c_1 = 2$、$c_2 = 3$（当 $n$ 足够大时 $2n^2 \le 2n^2+3n\log n \le 3n^2$）。
2. 内层次数 $= (n) + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}$，$O(n^2)$。
3. $f(n) = n\log n = \Omega(n^{0.79+\epsilon})$，情形 3，$T(n) = O(n\log n)$。
4. $T(n) = T(n-1)+T(n-2)+O(1)$，增长率为黄金分割比的幂，$O(\varphi^n) \approx O(1.618^n)$，指数级。