#绪论与复杂度分析

#考点定位

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

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

#渐进符号的数学表述

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

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

考试抠字眼的方式：

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

#考法一：循环计数

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

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、三层嵌套——统统归约为"内层次数求和"。

#考法二：递推展开

形如"每次规模减半再做 $$ 工作"：$$（这就是二分查找，也是选择题常客）。

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

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

记 $$，与 $$ 比较：

速用实例：

• 归并排序 $$：$$，$$ 与 $$ 同阶 → $$
• 二分查找 $$：$$，$$ 同阶 → $$
• 快速排序最好情况 $$ → $$；最坏 $$ 不满足主方法形式（$$ 不允许），直接展开为 $$

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

#例题（模拟题）

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

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

A. $$ B. $$ C. $$ D. $$

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

例 2：$$ 的渐进时间复杂度为（ ）

A. $$ B. $$ C. $$ D. $$

解答：$$，$$，情形 1，$$，选 C。

#常见坑

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

#自测

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

答案与简析

1. 成立。取 $$、$$（当 $$ 足够大时 $$）。
2. 内层次数 $$，$$。
3. $$，情形 3，$$。
4. $$，增长率为黄金分割比的幂，$$，指数级。