复杂度分析 · 考纲词条练习

考点：大 O 定义（A1）。

（A1）考点：$f(n) = O(g(n))$：存在 $c > 0$ 和 $n_0$，当 $n \ge n_0$ 时 $f(n) \le c \cdot g(n)$——$g(n)$ 是 $f(n)$ 的渐近上界。

解析：大 O 不是等式而是不等式：描述增长率的上限——"至多这么快增长"。核心条件是"当 $n$ 足够大时"（忽略小规模行为）。

排除法：选"等于"的人把上界当成了精确值；选"小于"的人漏了常数因子 $c$；选"无关"的人否定了约束关系。

考点：渐近上界含义（A2）。

（A2）考点："O(n²) 的算法"意味着操作次数至多与 $n^2$ 成正比（$n$ 足够大时）——是增长率上限。

解析：$3n^2 + 5n = O(n^2)$ 不仅是 $n^2$，所有以平方为上界的式子都属于 $O(n^2)$。

排除法：选"恰好 $n^2$" 的人忽略了低阶项与常数；选"至少"的人方向反（那是 $\Omega$）；选"等于 $n^2$ 毫秒"的人把复杂度等同于具体时间。

考点：Ω 与 Θ（A3）。

（A3）考点：$\Omega(g(n))$：渐近下界（至少这么快）；$\Theta(g(n))$：渐近紧确界（上下同阶）。$f = \Theta(g) \iff f = O(g) \text{ 且 } f = \Omega(g)$。

解析：$O$ 是"不超过"、$\Omega$ 是"不小于"、$\Theta$ 是"恰好"——三者从不同角度描述增长率。日常说"某算法是 O(n log n)"时，多数场合实际指 $\Theta(n \log n)$。

考点：常见量级排序（A4）。

（A4）考点：从慢到快：$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$——标准量级阶梯。

解析：每级之间的差距随 $n$ 增大而拉大：$n = 10^6$ 时 $O(n) \approx 10^6$、$O(n^2) = 10^{12}$、$O(2^n)$ 天文数字。

排除法：B 把 $\log n$ 排在 $n$ 之后反了；C 把 $O(1)$ 排在 $O(\log n)$ 之后反了；D 把 $n$ 排最前。

考点：量级比较（A5）。

（A5）考点：$n$ 足够大时 $O(n^2)$ 更大：$n^2 / (n \log n) = n / \log n \to \infty$——平方的增长速度压倒 $n \log n$。

解析：$\log n$ 是"缓慢增长"的函数（$n = 10^6$ 时 $\log_2 n \approx 20$），因此 $n \log n$ 远比 $n^2$ 慢。

考点：常数忽略（A6）。

（A6）考点：$O(2n) = O(n/2) = O(100n) = O(n)$——大 O 忽略常数因子。

解析：$f(n) / g(n) = c$（有限常数）时 $f = O(g)$——倍数关系不改变量级。

排除法：选 $O(1)$ 的人把"常数因子"当成了"常数时间"；选"$O(2n)$ 最精确"的人忘了大 O 本身就是忽略常数的记号。

考点：低阶项忽略（A7）。

（A7）考点：$3n^2 + 5n + 7 = O(n^2)$——只保留最高阶项，忽略系数与低阶项。

解析：$n \to \infty$ 时 $n^2$ 项占绝对主导（$5n / n^2 \to 0$）；低阶项对增长率无影响。

考点：大 O 加法（A8）。

（A8）考点：顺序执行的两段代码 $O(n)$ 与 $O(n^2)$：$O(n) + O(n^2) = O(\max) = O(n^2)$——顺序取最大。

解析：总代价 $= c_1 n + c_2 n^2$，$n$ 大时 $n^2$ 项压倒 $n$ 项。

排除法：选相乘 $O(n^3)$ 的人混淆了顺序与嵌套。

考点：大 O 乘法（A9）。

（A9）考点：外层 $O(n)$ 嵌套内层 $O(\log n)$：$O(n \times \log n) = O(n \log n)$——嵌套取乘积。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：O(1) 含义（A10）。

（A10）考点：$O(1)$ 表示执行时间与输入规模无关——常数时间（数组访问、加减、swap）。

排除法：$O(1)$ 不是"只执行一次"——是执行固定次数不随 $n$ 变。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：对数的底（A11）。

（A11）考点：$O(\log_2 n) = O(\log_{10} n) = O(\log n)$——换底只差常数因子，大 O 统一写 $\log n$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：输入规模 n（A12）。

（A12）考点：$n$ 指的是输入规模——数组长度、图的顶点数/边数、字符串长度等度量问题大小的量。

排除法：代码行数、秒数、测试组数都不是复杂度分析的 $n$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：单层循环 O(n)（B1）。

（B1）考点：单层 for i < n 循环执行 $n$ 次——$O(n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：嵌套循环 O(n²)（B2）。

（B2）考点：两层独立嵌套各 $n$ 次：$n \times n = n^2$——$O(n^2)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：三层循环 O(n³)（B3）。

（B3）考点：三层独立嵌套各 $n$ 次：$n^3$——$O(n^3)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：j*=2 对数循环（B4）。

（B4）考点：j *= 2 使 $j$ 每次翻倍：$1, 2, 4, \ldots, 2^k \ge n$ 时结束——循环 $\log_2 n$ 次，$O(\log n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：j/=2 对数循环（B5）。

（B5）考点：j /= 2 同理每次减半：$\log n$ 次结束。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：i*i<n 开方循环（B6）。

（B6）考点：i*i < n 等价于 $i < \sqrt{n}$——循环 $\sqrt{n}$ 次，$O(\sqrt{n})$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：混合内外层（B7）。

（B7）考点：外层 $n$ 次 × 内层 j *= 2 $\log n$ 次 = $O(n \log n)$。（2022 年真题考法）

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：双变量相向（B8）。

（B8）考点：i++; j-- 双指针从两端相向：共走 $n/2$ 步——$O(n)$（常数 $\frac{1}{2}$ 忽略）。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：内层依赖外层（B9）。

（B9）考点：内层 j < i 依赖外层 $i$：总次数 $0+1+\cdots+(n-1) = \frac{n(n-1)}{2}$——$O(n^2)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：代码段综合真题（B10）。

（B10）考点：外层 i++ $n$ 次 × 内层 j *= 2（注意初值 $j=0$，$j$ 乘 $2$ 恒为 $0$，循环不终止——但真题中初值为 $1$ 时内层 $\log n$ 次）：整体 $O(n \log n)$。（2022 年 S 组真题原题，考识别对数型内层）

排除法：选 $O(n)$ 的人没看到嵌套；选 $O(n^2)$ 的人误判内层为线性。

考点：while 循环复杂度（B11）。

（B11）考点：n = n / 3 每次除以 $3$：$3^k \ge n$ 时结束——$O(\log n)$（底 $3$ 与底 $2$ 同阶）。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：连续循环取最大（B12）。

（B12）考点：两段顺序执行 $O(n)$ 与 $O(n^2)$——取最大 $O(n^2)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：常数次操作（B13）。

（B13）考点：固定几步操作（swap、输出）不随 $n$ 变——$O(1)$。

排除法：选 $O(2)$ 的人大 O 不写具体常数。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：循环综合判断（B14）。

（B14）考点：嵌套取乘积 ✓、顺序取最大 ✓、j *= 2 对数 ✓；"所有嵌套都是 $O(n^2)$"错误——嵌套的复杂度取决于内层增长率（如外 $n$ 内 $\log n$ 得 $n \log n$）。

考点：递归树方法（C1）。

（C1）考点：递归树方法：逐层展开递归、计算每层总代价、所有层求和即总复杂度。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：单分支递归 O(n)（C2）。

（C2）考点：f(n-1) 单分支每次减 $1$：递归 $n$ 层、每层 $O(1)$——$O(n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：二分递归 O(log n)（C3）。

（C3）考点：f(n/2) 单分支每次减半：递归 $\log n$ 层、每层 $O(1)$——$O(\log n)$（二分查找递归式）。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：双子递归 O(2ⁿ)（C4）。

（C4）考点：fib(n-1) + fib(n-2) 双子树：递归树节点数指数增长——$O(2^n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：主定理形式（C5）。

（C5）考点：$T(n) = aT(n/b) + O(n^d)$：$a$ 是子问题个数、$b$ 是规模缩小倍数、$d$ 是每层合并代价。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：主定理 T(n)=2T(n/2)+O(n)（C6）。

（C6）考点：$a = 2, b = 2, d = 1$，$a = b^d = 2$：每层代价 $O(n)$ × $\log n$ 层 = $O(n \log n)$——归并排序递归式。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：主定理 T(n)=2T(n/2)+O(1)（C7）。

（C7）考点：$a = 2, b = 2, d = 0$，$a > b^d = 1$：叶节点主导 $2^{\log n} = n$ 个叶各 $O(1)$ = $O(n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：主定理 T(n)=T(n/2)+O(1)（C8）。

（C8）考点：$a = 1, b = 2, d = 0$，$a = b^d = 1$：$\log n$ 层每层 $O(1)$ = $O(\log n)$——二分查找。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：递归深度与栈空间（C9）。

（C9）考点：递归深度 $d$、每帧 $O(1)$ 局部变量：栈空间 $O(d)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：斐波那契递归复杂度（C10）。

（C10）考点：朴素斐波那契 $O(2^n)$：$n = 40$ 时约 $2^{40} \approx 10^{12}$ 次调用——普通电脑需数秒到数十秒。

排除法：选"瞬间完成"的人低估了指数爆炸；选"$40$ GB"的人把时间混淆为空间。

考点：归并排序递归式（C11）。

（C11）考点：归并排序 $T(n) = 2T(n/2) + O(n)$，$a = b^d = 2$，解 $O(n \log n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：递归综合判断（C12）。

（C12）考点："所有递归都比循环慢"错误——递归与循环是同一逻辑的两种表达；编译器可优化尾递归为循环；实际速度取决于编译器与硬件。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：冒泡复杂度（D1）。

（D1）考点：冒泡排序平均与最坏均 $O(n^2)$——最好 $O(n)$ 需提前退出优化。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：插入复杂度（D2）。

（D2）考点：插入排序最好 $O(n)$（基本有序）、最坏 $O(n^2)$（完全逆序）。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：归并复杂度（D3）。

（D3）考点：归并排序最好、平均、最坏均为 $O(n \log n)$——分区永远对半、与数据无关。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：快排复杂度（D4）。

（D4）考点：快排最坏 $O(n^2)$（已序+首元素基准）——平均 $O(n \log n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：堆排复杂度（D5）。

（D5）考点：堆排最好、平均、最坏均为 $O(n \log n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：计数排序复杂度（D6）。

（D6）考点：计数排序 $O(n + V)$——非比较类，不受 $n \log n$ 下界约束。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：比较排序下界（D7）。

（D7）考点：基于比较的排序最坏比较次数下界 $\Omega(n \log n)$——$n!$ 种排列、每次比较至多砍半。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：排序复杂度对比表（D8）。

（D8）考点：最坏仍 $O(n \log n)$ 的排序：归并与堆排；快排最坏退化 $O(n^2)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：空间复杂度定义（E1）。

（E1）考点：空间复杂度 $=$ 算法执行过程中占用的额外存储空间随 $n$ 的增长率。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：数组空间计算（E2）。

（E2）考点：int a[10000] 大小固定 $10000 \times 4$ 字节——$O(1)$（不随 $n$ 变）。

排除法：选 $O(10000)$ 的人大 O 不写具体数字。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：二维数组空间（E3）。

（E3）考点：int g[n][n] 大小 $n^2 \times 4$——$O(n^2)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：递归栈空间（E4）。

（E4）考点：递归深度 $n$、每帧 $O(1)$：栈空间 $O(n)$。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。

考点：原地排序空间（E5）。

（E5）考点：冒泡/插入/快排均为 $O(1)$ 额外空间（原地排序）。

解析补充：本题考查复杂度分析的核心概念。掌握大 O 记号的定义与运算规则（嵌套取乘积、顺序取最大、忽略常数与低阶项）是分析代码的基础。