题目导航

林老师 · 客观题题库 · 专题 S03 复杂度分析 · 复习强化

专题 S03 复杂度分析 · 复习强化

100 题 · 每题对应一个知识细节 · 全部原创

真题
复刻

试卷编号ORIG-专题S03复杂度分析-复习强化

题目总数103 题 · 100 分

试卷类型客观题

考生须知：
① 本卷共 10 大部分，合计 103 题 · 100 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。

判分报告

0 / 100 分

答对 · 得 0 分

答错 · 失 0 分

未作答

当前筛选下没有题目

壹

Big O 与渐近记号

12 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

$f(n) = O(g(n))$ 的含义是（）。

（1 分）

$f(n)$ 与 $g(n)$ 无关

$f(n)$ 等于 $g(n)$

$f(n)$ 小于 $g(n)$

存在常数 $c$ 和 $n_0$ ，当 $n \ge n_0$ 时 $f(n) \le c \cdot g(n)$ —— $g(n)$ 是 $f(n)$ 的渐近上界

第 2 题 A2 未作答

"O(n²) 的算法"意味着（）。

（1 分）

执行时间恰好等于 $n^2$ 毫秒

操作次数至多与 $n^2$ 成正比（当 $n$ 足够大时）——是增长率的上限

至少执行 $n^2$ 次操作

恰好执行 $n^2$ 次操作

第 3 题 A3 未作答

$\Omega(g(n))$ 与 $\Theta(g(n))$ 分别表示（）。

（1 分）

$\Omega$ ：渐近下界（至少这么快）； $\Theta$ ：渐近紧确界（上下界同阶）

两者含义相同

$\Omega$ ：精确值， $\Theta$ ：估计值

$\Omega$ ：上界， $\Theta$ ：下界

第 4 题 A4 未作答

按增长速度从慢到快排列，正确的是（）。

（1 分）

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$

$O(n) < O(1) < O(\log n) < O(n \log n) < O(n^2)$

$O(\log n) < O(1) < O(n) < O(2^n) < O(n^2) < O(n!)$

$O(1) < O(n) < O(\log n) < O(n^2) < O(n \log n) < O(2^n)$

第 5 题 A5 未作答

当 $n$ 足够大时， $O(n \log n)$ 与 $O(n^2)$ 的关系是（）。

（1 分）

$O(n \log n)$ 更大

两者相等

取决于具体实现

$O(n^2)$ 更大—— $n^2 / (n \log n) = n / \log n \to \infty$

第 6 题 A6 未作答

$O(2n)$ 、 $O(n/2)$ 、 $O(100n)$ 统一写成（）。

（1 分）

$O(n)$ ——大 O 忽略常数因子

$O(1)$

$O(2n)$ 最精确

三者互不相同

第 7 题 A7 未作答

$f(n) = 3n^2 + 5n + 7$ 的渐近复杂度是（）。

（1 分）

$O(n^2 + n)$

$O(3n^2 + 5n + 7)$

$O(n)$

$O(n^2)$ ——只保留最高阶项，忽略系数与低阶项

第 8 题 A8 未作答

两段代码分别 $O(n)$ 和 $O(n^2)$ ，顺序执行的整体复杂度是（）。

（1 分）

$O(n)$

$O(n^2)$ ——顺序执行取最大项： $O(n) + O(n^2) = O(\max(n, n^2)) = O(n^2)$

$O(n \times n^2) = O(n^3)$

$O(n + n^2)$ 不能化简

第 9 题 A9 未作答

外层循环 $O(n)$ 内嵌循环 $O(\log n)$ （嵌套），整体复杂度是（）。

（1 分）

$O(\log n)$

$O(n \log n)$ ——嵌套取乘积

$O(n + \log n)$

$O(n)$

第 10 题 A10 未作答

$O(1)$ 表示（）。

（1 分）

只执行一次

输入只有一个元素

执行时间与输入规模无关——常数时间（如数组访问、加减运算、swap）

时间为 $1$ 毫秒

第 11 题 A11 未作答

$O(\log_2 n)$ 与 $O(\log_{10} n)$ 的关系是（）。

（1 分）

无法比较

$\log_2 n$ 更大，两者不同阶

$\log_{10} n$ 更大

同阶——换底公式 $\log_2 n = \log_{10} n / \log_{10} 2$ ，只差常数因子，大 O 统一写 $O(\log n)$

第 12 题 A12 未作答

复杂度分析中的 $n$ 指的是（）。

（1 分）

输入规模——数组长度、图的顶点数/边数、字符串长度等度量问题大小的量

测试数据的组数

程序代码的行数

运行时间（秒）

贰

循环与代码段分析

14 QUESTIONS · 2 POINTS EACH

第 13 题 B1 未作答

01for (int i = 0; i < n; ++i)
02    sum += a[i];

时间复杂度是（）。

（1 分）

$O(n)$

$O(1)$

$O(n^2)$

$O(\log n)$

第 14 题 B2 未作答

01for (int i = 0; i < n; ++i)
02    for (int j = 0; j < n; ++j)
03        cnt++;

时间复杂度是（）。

（1 分）

$O(n)$

$O(2n)$

$O(n^2)$

$O(n \log n)$

第 15 题 B3 未作答

三层独立嵌套循环，每层 $n$ 次，时间复杂度是（）。

（1 分）

$O(n^2)$

$O(n^3)$

$O(n \log n)$

$O(3n)$

第 16 题 B4 未作答

01for (int j = 1; j < n; j *= 2)
02    k++;

循环执行次数约为（），时间复杂度是（）。

（1 分）

$n$ 次， $O(n)$

$2n$ 次， $O(n)$

$n/2$ 次， $O(n)$

$\log_2 n$ 次， $O(\log n)$ —— $j$ 每次翻倍， $2^k \ge n$ 时结束

第 17 题 B5 未作答

01for (int j = n; j > 0; j /= 2)
02    k++;

时间复杂度是（）。

（1 分）

$O(\log n)$

$O(n)$

$O(n \log n)$

$O(n/2)$

第 18 题 B6 未作答

01for (int i = 1; i * i < n; ++i)
02    k++;

时间复杂度是（）。

（1 分）

$O(n)$

$O(\sqrt{n})$ ——循环到 $\sqrt{n}$ 就满足 $i^2 \ge n$

$O(\log n)$

$O(n^2)$

第 19 题 B7 未作答

01for (int i = 0; i < n; ++i)
02    for (int j = 1; j < n; j *= 2)
03        k++;

时间复杂度是（）。（2022 年 S 组真题考法）

（1 分）

$O(n)$

$O(n^2)$

$O(n \log n)$ ——外层 $n$ 次乘内层 $\log n$ 次

$O(\log n)$

第 20 题 B8 未作答

01int i = 0, j = n - 1;
02while (i < j) { i++; j--; }

时间复杂度是（）。

（1 分）

$O(n)$ ——两个指针从两端相向而行，共走约 $n/2$ 步

$O(\log n)$

$O(n^2)$

$O(n/4)$

第 21 题 B9 未作答

01for (int i = 0; i < n; ++i)
02    for (int j = 0; j < i; ++j)
03        cnt++;

时间复杂度是（）。

（1 分）

$O(n \log n)$

$O(n)$

$O(n^2)$ ——内层共执行 $0+1+2+\cdots+(n-1) = n(n-1)/2$ 次

$O(n^3)$

第 22 题 B10 未作答

01int i, j, k = 0;
02for (i = 0; i < n; i++) {
03    for (j = 0; j < n; j *= 2) {
04        k = k + n / 2;
05    }
06}

时间复杂度是（）。（2022 年 CSP-S 单选真题）

（1 分）

$O(n\log n)$

$O(n^2)$

$O(n\sqrt{n})$

$O(n)$

第 23 题 B11 未作答

01while (n > 1) { n = n / 3; }

时间复杂度是（）。

（1 分）

$O(3n)$

$O(\log n)$ ——每次除以 $3$ ， $3^k \ge n$ 时结束（底数为 $3$ 的对数与 $2$ 同阶）

$O(n)$

$O(n/3)$

第 24 题 B12 未作答

01for (int i = 0; i < n; ++i) a[i]++;
02for (int i = 0; i < n * n; ++i) b[i]++;

整体时间复杂度是（）。

（1 分）

$O(n + n^2)$ 不能化简

$O(n^3)$

$O(n^2)$ ——顺序执行取最大项

$O(n)$

第 25 题 B13 未作答

01int a = 1, b = 2;
02swap(a, b);
03cout << a << b;

时间复杂度是（）。

（1 分）

$O(2)$

$O(n)$

$O(\log 2)$

$O(1)$ ——操作次数固定不随 $n$ 变化

第 26 题 B14 未作答

关于循环复杂度，错误的说法是（）。

（1 分）

顺序循环取最大

$j *= 2$ 型循环是对数级

嵌套循环取乘积

所有嵌套循环都是 $O(n^2)$

叁

递归复杂度

12 QUESTIONS · 2 POINTS EACH

第 27 题 C1 未作答

分析递归复杂度的"递归树"方法的核心思想是（）。

（1 分）

画出函数调用图数节点

只看最深层

逐层展开递归：每层分解为子问题、计算每层总代价，所有层代价求和即总复杂度

只看叶子层

第 28 题 C2 未作答

01int f(int n) {
02    if (n <= 1) return 1;
03    return f(n - 1) + 1;
04}

时间复杂度是（）。

（1 分）

$O(2^n)$

$O(\log n)$

$O(1)$

$O(n)$ ——递归 $n$ 层、每层 $O(1)$

第 29 题 C3 未作答

01int f(int n) {
02    if (n <= 1) return 1;
03    return f(n / 2) + 1;
04}

时间复杂度是（）。

（1 分）

$O(\log n)$ ——每次问题规模减半，递归 $\log n$ 层

$O(n/2)$

$O(2^n)$

$O(n)$

第 30 题 C4 未作答

01int fib(int n) {
02    if (n <= 1) return n;
03    return fib(n-1) + fib(n-2);
04}

时间复杂度约是（）。

（1 分）

$O(2^n)$ ——每个节点分裂两个子节点，递归树节点数指数增长

$O(n^2)$

$O(n \log n)$

$O(n)$

第 31 题 C5 未作答

主定理（Master Theorem）处理形如 $T(n) = aT(n/b) + O(n^d)$ 的递归式，其中 $a$ 、 $b$ 、 $d$ 的含义分别是（）。

（1 分）

$a$ 是递归深度， $b$ 是子问题结果， $d$ 是输入规模

$a$ 是答案， $b$ 是递归式， $d$ 是深度

$a$ 是子问题个数（每次分成几个子问题）， $b$ 是规模缩小倍数（每个子问题是原问题的 $1/b$ ）， $d$ 是每层合并代价的次数

三者是任意常数

第 32 题 C6 未作答

$T(n) = 2T(n/2) + O(n)$ 的解是（）。

（1 分）

$O(\log n)$

$O(n^2)$

$O(n)$

$O(n \log n)$ —— $a = b^d = 2$ ，每层代价 $O(n)$ 、共 $\log n$ 层（归并排序的递归式）

第 33 题 C7 未作答

$T(n) = 2T(n/2) + O(1)$ 的解是（）。

（1 分）

$O(n)$ —— $a = 2 > b^d = 1$ ，叶节点主导： $2^{\log n} = n$ 个叶子各 $O(1)$

$O(\log n)$

$O(n)$

$O(n \log n)$

第 34 题 C8 未作答

$T(n) = T(n/2) + O(1)$ 的解是（）。

（1 分）

$O(n \log n)$

$O(n)$

$O(\log n)$ ——单分支每次减半， $\log n$ 层每层 $O(1)$ （二分查找的递归式）

$O(2^n)$

第 35 题 C9 未作答

递归深度为 $d$ 的递归函数，栈空间复杂度是（）（每帧 $O(1)$ 局部变量）。

（1 分）

$O(n)$ 无论深度

$O(1)$

$O(d^2)$

$O(d)$ ——每个递归调用帧入栈，栈深 $=$ 递归深度

第 36 题 C10 未作答

朴素斐波那契递归 fib(40) 在普通电脑上（）。

（1 分）

瞬间完成

需要数秒到数十秒—— $O(2^n)$ 的指数爆炸让 $n=40$ 时调用约 $2^{40} \approx 10^{12}$ 次

需要内存 $40$ GB

只能用迭代算

第 37 题 C11 未作答

归并排序的递归式与主定理求解结果是（）。

（1 分）

$T(n) = 2T(n) + O(1)$ ，无解

$T(n) = T(n/2) + O(n)$ ，解 $O(n)$

$T(n) = 2T(n/2) + O(n)$ ，解 $O(n \log n)$ —— $a=2, b=2, d=1$ ， $a=b^d$ 平衡

$T(n) = T(n-1) + O(n)$ ，解 $O(n^2)$

第 38 题 C12 未作答

关于递归复杂度，错误的说法是（）。

（1 分）

双子递归每层减一是 $O(2^n)$

所有递归都比循环慢

单分支递归每层减半是 $O(\log n)$

双子递归每层减半合并 $O(n)$ 是 $O(n \log n)$

肆

排序复杂度回顾

8 QUESTIONS · 2 POINTS EACH

第 39 题 D1 未作答

冒泡排序的平均与最坏时间复杂度是（）。

（1 分）

$O(n^2)$ 、 $O(n^3)$

$O(n \log n)$ 、 $O(n^2)$

$O(n)$ 、 $O(n^2)$

$O(n^2)$ 、 $O(n^2)$

第 40 题 D2 未作答

插入排序的最好与最坏时间复杂度是（）。

（1 分）

$O(n \log n)$ 、 $O(n^2)$

$O(n)$ 、 $O(n^2)$

都是 $O(n^2)$

$O(n)$ 、 $O(n^2)$ ——但这是带"基本有序时近线性"特性的

第 41 题 D3 未作答

归并排序的最好、平均、最坏时间复杂度是（）。

（1 分）

$O(n \log n)$ 、 $O(n \log n)$ 、 $O(n \log n)$ ——与数据无关

$O(n)$ 、 $O(n \log n)$ 、 $O(n^2)$

无法确定

$O(n \log n)$ 、 $O(n \log n)$ 、 $O(n^2)$

第 42 题 D4 未作答

快速排序的最坏时间复杂度是（）。

（1 分）

$O(n \log^2 n)$

$O(n \log n)$

$O(n^2)$ ——已序输入配首元素基准时退化

$O(n)$

第 43 题 D5 未作答

堆排序的最好、平均、最坏时间复杂度是（）。

（1 分）

$O(n \log n)$ 、 $O(n \log n)$ 、 $O(n^2)$

$O(n \log n)$ 、 $O(n \log n)$ 、 $O(n \log n)$

都是 $O(n^2)$

$O(n)$ 、 $O(n \log n)$ 、 $O(n \log n)$

第 44 题 D6 未作答

计数排序的时间复杂度是（）（ $n$ 个元素、值域 $V$ ）。

（1 分）

$O(n \log n)$

$O(V \log V)$

$O(n + V)$

$O(n^2)$

第 45 题 D7 未作答

基于比较的排序算法，最坏情况的比较次数下界是（）。

（1 分）

$O(n^2)$

$O(n)$

没有下界

$\Omega(n \log n)$

第 46 题 D8 未作答

以下排序算法中，最坏情况仍保持 $O(n \log n)$ 的是（）。

（1 分）

冒泡排序

插入排序

归并排序与堆排序

快速排序

伍

空间复杂度

10 QUESTIONS · 2 POINTS EACH

第 47 题 E1 未作答

算法的空间复杂度指的是（）。

（1 分）

代码占多少 KB

程序编译后的大小

硬盘容量

算法执行过程中占用的额外存储空间随输入规模 $n$ 的增长率——用大 O 记号表示

第 48 题 E2 未作答

int a[10000]; 的空间复杂度是（）。

（1 分）

$O(n^2)$

$O(n)$

$O(10000)$

$O(1)$ ——数组大小固定（ $10000 \times 4$ 字节），不随输入规模变化

第 49 题 E3 未作答

int g[n][n];（ $n$ 是运行时输入）的空间复杂度是（）。

（1 分）

$O(n \log n)$

$O(2n)$

$O(n^2)$

$O(n)$

第 50 题 E4 未作答

递归深度为 $n$ 的函数（每帧 $O(1)$ 变量），空间复杂度是（）。

（1 分）

$O(n^2)$

$O(n)$ ——栈中同时存在 $n$ 个递归帧

$O(\log n)$

$O(1)$

第 51 题 E5 未作答

冒泡排序、插入排序、快速排序的共同空间特征是（）。

（1 分）

$O(1)$ 额外空间（原地排序，只用常数个临时变量）

不需要任何空间

$O(n \log n)$ 额外空间

$O(n)$ 额外空间

第 52 题 E6 未作答

归并排序的空间复杂度是（）。

（1 分）

$O(\log n)$

$O(n \log n)$

$O(1)$

$O(n)$ ——合并时需要临时数组存放两段合并结果

第 53 题 E7 未作答

vector<int> v; 依次 push_back $n$ 个元素，最坏情况下 vector 的空间复杂度是（）。

（1 分）

$O(1)$

$O(n)$ ——vector 按倍增策略扩容，最大时占 $O(n)$ 空间

$O(n^2)$

$O(n \log n)$

第 54 题 E8 未作答

"空间换时间"的典型例子是（）。

（1 分）

用 $O(n)$ 数组做哈希表/标记数组，把 $O(n^2)$ 的查找降为 $O(1)$ ——多花内存少花时间

不用递归改用循环

减少循环次数

用更快的 CPU

第 55 题 E9 未作答

$n = 10^5$ 时， $O(n^2)$ 的 int 二维数组约需（）。

（1 分）

$4$ MB

$40$ MB

$4$ KB

$40$ GB—— $10^{10} \times 4$ 字节远超内存，开不出

第 56 题 E10 未作答

关于空间复杂度，错误的是（）。

（1 分）

原地排序额外空间 $O(1)$

递归深度 $d$ 则栈空间 $O(d)$

int a[1000000]; 的空间复杂度是 $O(n)$

归并排序需要 $O(n)$ 辅助数组

陆

记忆化搜索

10 QUESTIONS · 2 POINTS EACH

第 57 题 F1 未作答

记忆化搜索的核心思想是（）。

（1 分）

只做一次递归

用数组/哈希表缓存已计算的子问题结果，再次遇到时直接查表——避免重复递归

改用循环替代递归

多线程加速

第 58 题 F2 未作答

记忆化搜索最适合的场景是（）。

（1 分）

子问题各不相同

递归中存在大量重复子问题（如斐波那契、背包、棋盘路径计数）

需要精确浮点结果

递归深度很浅

第 59 题 F3 未作答

朴素斐波那契递归是 $O(2^n)$ ；加记忆化后时间复杂度变为（）。

（1 分）

$O(2^n)$ 不变

$O(\log n)$

$O(n)$ ——每个 $f(k)$ 只算一次，共 $n$ 个状态

$O(n \log n)$

第 60 题 F4 未作答

记忆化搜索中标记数组 memo[n] 的初始值与含义是（）。

（1 分）

初始化为 $0$ ，表示"已计算且结果为 $0$ "

标记数组存递归深度

不需要标记数组

初始化为特殊值（如 $-1$ ），表示"未计算"；计算后存入真实值，下次遇到直接返回

第 61 题 F5 未作答

记忆化搜索与递推（动态规划）的关系是（）。

（1 分）

记忆化是"自顶向下"的动态规划——从大问题向下递归、算完即存；递推是"自底向上"从小到大填表。两者本质等价，复杂度相同

记忆化不能解决 DP 问题

两者完全无关

记忆化永远比递推快

第 62 题 F6 未作答

记忆化搜索把斐波那契从 $O(2^n)$ 降到 $O(n)$ ，改善的关键在于（）。

（1 分）

把递归变成了循环

每个状态只计算一次—— $n$ 个状态各 $O(1)$ 次计算，总 $O(n)$ （原来是指数次重复计算）

提高了 CPU 利用率

减少了递归深度

第 63 题 F7 未作答

记忆化搜索代码的标准框架是（）。

（1 分）

01for (int i = 0; i < n; ++i) f[i] = f[i-1] + f[i-2];

01int f(int n) { return f(n-1) + f(n-2); }

01int f(int n) { return n * (n-1); }

01int memo[N];
02int f(int n) {
03    if (n <= 1) return n;
04    if (memo[n] != -1) return memo[n]; // 已算过，直接返回
05    return memo[n] = f(n-1) + f(n-2); // 算完存入
06}

第 64 题 F8 未作答

记忆化与普通递归的根本区别是（）。

（1 分）

普通递归可能重复计算同一子问题；记忆化保证每个子问题只算一次、后续直接查表

没有区别

记忆化只能用于数学函数

记忆化不用递归

第 65 题 F9 未作答

记忆化适用的必要条件是（）。

（1 分）

问题有贪心策略

数据规模小于 $100$

子问题具有最优子结构且存在重叠子问题——不重叠则无重复可省

问题必须与树有关

第 66 题 F10 未作答

关于记忆化搜索，错误的是（）。

（1 分）

记忆化本质是自顶向下的 DP

记忆化后复杂度一定变为 $O(1)$

记忆化需要额外 $O(\text{状态数})$ 空间

记忆化可以把 $O(2^n)$ 降为 $O(n)$

柒

剪枝优化

10 QUESTIONS · 2 POINTS EACH

第 67 题 G1 未作答

搜索算法中的"剪枝"指的是（）。

（1 分）

加速 I/O

在搜索过程中提前排除不可能产生解的分支——"剪掉"无用的子树，减少搜索空间

删除代码中无用的行

把树变成链

第 68 题 G2 未作答

"当前已选数之和已超过目标 $t$ ，直接 return"——这是哪种剪枝（）。

（1 分）

可行性剪枝——当前状态已不满足约束条件，沿此分支不可能有解

记忆化剪枝

最优性剪枝

搜索顺序剪枝

第 69 题 G3 未作答

"求最大值时，当前价值加剩余全选仍 $\le$ 当前最优，剪掉"——这是（）。

（1 分）

随机化

最优性剪枝（也叫上界剪枝）——即使走到最好也不可能超过已有答案，继续搜索无意义

对称性剪枝

可行性剪枝

第 70 题 G4 未作答

"先试较大的候选数再试较小的"——这属于（）。

（1 分）

最优性剪枝

可行性剪枝

搜索顺序剪枝——调整尝试顺序使好分支先走、坏分支更早暴露被剪

不是剪枝

第 71 题 G5 未作答

$\alpha$ - $\beta$ 剪枝用于（）。

（1 分）

字符串匹配

最短路算法

排序算法

博弈树搜索——最大化层维护 $\alpha$ （当前最优下界）、最小化层维护 $\beta$ （当前最优上界）， $\alpha \ge \beta$ 时剪掉剩余分支

第 72 题 G6 未作答

正确的剪枝不会改变算法的正确性，原因是（）。

（1 分）

被剪掉的分支保证不包含更优解（可行性剪枝去掉无解分支、最优性剪枝去掉不优于已知解的分支）——留下的搜索空间仍包含最优解

凭运气

剪枝只影响速度

剪枝后重新搜索

第 73 题 G7 未作答

剪枝的加速效果通常用（）来衡量。

（1 分）

CPU 温度降低

搜索树实际访问的节点数减少比例——好的剪枝可把指数级搜索空间砍到可行范围内

代码行数减少

内存占用减少

第 74 题 G8 未作答

不剪枝的 DFS 在解空间为排列（ $n!$ ）时， $n = 12$ 的搜索量约是（）。

（1 分）

$12! \approx 4.79 \times 10^8$ ——不剪枝几乎不可行，必须剪枝

$12 \times 2 = 24$

$2^{12} \approx 4096$

$12^2 = 144$

第 75 题 G9 未作答

从若干正整数中选一些使和恰好为 $t$ ，DFS 搜索时应在什么条件下剪枝（）。

（1 分）

当 sum < t 时剪枝

当 sum == t 时剪枝

当 sum > t 时剪枝（正整数只会越加越大，不可能回到 $t$ ）——可行性剪枝

不需要剪枝

第 76 题 G10 未作答

关于剪枝，错误的是（）。

（1 分）

剪枝可以去掉可能包含最优解的分支

最优性剪枝去掉不优于已有答案的分支

可行性剪枝去掉无解分支

搜索顺序剪枝不改变解但影响剪枝效率

捌

分治

10 QUESTIONS · 2 POINTS EACH

第 77 题 H1 未作答

分治法的三个步骤是（）。

（1 分）

分（Divide）：把问题分成若干子问题 → 治（Conquer）：递归解决子问题 → 合（Combine）：合并子问题的解

比较→交换→移动

输入→处理→输出

分析→设计→编码

第 78 题 H2 未作答

分治与递归的关系是（）。

（1 分）

分治必须用循环

分治通常用递归实现——"分"就是递归调用自身处理子问题；但递归不一定是分治（如单分支递归就没有"分"）

两者无关

递归是分治的另一种说法

第 79 题 H3 未作答

归并排序中"分"与"合"分别指（）。

（1 分）

比较与交换

排序与查找

分：把数组对半拆到单元素；合：把两个有序段合并成更长的有序段

建堆与取顶

第 80 题 H4 未作答

快速排序中"分"的具体操作是（）。

（1 分）

分区（partition）：选基准，小于基准的放左、大于的放右，基准落位——左右两区再递归

放入桶中

对半拆

逐个比较相邻元素

第 81 题 H5 未作答

二分查找也可以看作分治，它的递归式与复杂度是（）。

（1 分）

$O(n^2)$

$T(n) = T(n-1) + O(1)$ ， $O(n)$

$T(n) = 2T(n/2) + O(n)$ ， $O(n \log n)$

$T(n) = T(n/2) + O(1)$ ， $O(\log n)$ ——每次只保留一半

第 82 题 H6 未作答

适合用分治法的问题应满足的条件不包括（）。

（1 分）

子问题之间必须有交集

子问题相互独立（不共享子子问题）

问题可以分解为若干规模更小的同类子问题

子问题的解可以合并为原问题的解

第 83 题 H7 未作答

分治算法的复杂度取决于（）。

（1 分）

只取决于递归深度

只取决于输入数据

子问题个数 $a$ 、规模缩小倍数 $b$ 、每层合并代价 $O(n^d)$ ——三者共同决定（主定理）

只取决于子问题个数

第 84 题 H8 未作答

主定理中 $a$ 与 $b^d$ 的比较决定了复杂度的"档位"： $a = b^d$ 时是（）。

（1 分）

$O(n^{\log_b a})$ ——根重

$O(n)$ ——叶重

$O(n^d \log n)$ ——每层代价相同、乘以层数（如归并排序 $a=2=b^1$ 得 $O(n \log n)$ ）

$O(2^n)$

第 85 题 H9 未作答

下列问题中，典型用分治法解决的是（）。

（1 分）

动态规划背包

Dijkstra 最短路

冒泡排序

归并排序、快速排序、二分查找

第 86 题 H10 未作答

关于分治，错误的是（）。

（1 分）

分治的复杂度可用主定理分析

归并排序是分治的典型应用

所有问题都可以用分治高效解决

分治三步骤：分、治、合

玖

综合分析

14 QUESTIONS · 2 POINTS EACH

第 87 题 I1 未作答

01for (int i = 0; i < n; ++i)
02    for (int j = i; j < n; ++j)
03        k++;

时间复杂度是（）。

（1 分）

$O(n \log n)$

$O(n^2)$ ——内层共执行 $n + (n-1) + \cdots + 1 = n(n+1)/2$ 次

$O(n)$

$O(n^3)$

第 88 题 I2 未作答

01for (int i = 1; i <= n; ++i)
02    for (int j = 1; j <= n; j += i)
03        k++;

时间复杂度是（）（调和级数 $\sum_{i=1}^{n} n/i \approx n \ln n$ ）。

（1 分）

$O(n^2)$

$O(\sqrt{n})$

$O(n)$

$O(n \log n)$ ——内层对每个 $i$ 执行 $n/i$ 次，总和是调和级数

第 89 题 I3 未作答

01void f(int n) {
02    if (n <= 1) return;
03    f(n / 2);
04    f(n / 2);
05    for (int i = 0; i < n; ++i) k++;
06}

时间复杂度是（）。

（1 分）

$O(n)$

$O(n \log n)$ —— $T(n) = 2T(n/2) + O(n)$ ，主定理 $a = b^d = 2$ 平衡

$O(n^2)$

$O(2^n)$

第 90 题 I4 未作答

在 $n$ 个数的无序数组中找最大元素，最少需要（）次比较。

（1 分）

$n$

$n \log n$

$\frac{n}{2}$

$n - 1$ ——每个元素至少被比较一次（除第一个），擂台法恰需 $n-1$ 次（2022 年 S 组真题）

第 91 题 I5 未作答

01void g(int n) {
02    if (n <= 0) return;
03    for (int i = 0; i < n; ++i) k++;
04    g(n / 2);
05}

时间复杂度是（）。

（1 分）

$O(n \log n)$

$O(n)$

$O(n)$ —— $T(n) = T(n/2) + O(n)$ ，总代价 $n + n/2 + n/4 + \cdots < 2n$

$O(n^2)$

第 92 题 I6 未作答

01int c = 0;
02for (int i = 1; i * i <= n; ++i)
03    for (int j = 1; j <= n; j *= 3)
04        c++;

时间复杂度是（）。

（1 分）

$O(n \log n)$

$O(\sqrt{n} \cdot \log n)$ ——外层 $\sqrt{n}$ 次乘内层 $\log_3 n$ 次

$O(n)$

$O(\sqrt{n})$

第 93 题 I7 未作答

将 $O(n!)$ 、 $O(2^n)$ 、 $O(n^3)$ 、 $O(n^2 \log n)$ 、 $O(n \log n)$ 按增长从慢到快排列，正确的是（）。

（1 分）

$O(2^n) < O(n!) < O(n \log n) < O(n^2 \log n) < O(n^3)$

$O(n \log n) < O(n^2 \log n) < O(n^3) < O(2^n) < O(n!)$

$O(n!) < O(2^n) < O(n^3) < O(n \log n) < O(n^2 \log n)$

$O(n \log n) < O(n^3) < O(n^2 \log n) < O(2^n) < O(n!)$

第 94 题 I8 未作答

$n = 10^6$ 、时限 $1$ 秒（约 $10^8$ 次运算）， $O(n \log n)$ 的算法（）。

（1 分）

可以通过—— $10^6 \times 20 \approx 2 \times 10^7$ 次，远小于 $10^8$

刚好卡在边界

无法判断

超时

第 95 题 I9 未作答

$O(1)$ 算法一定比 $O(n)$ 快，这个说法（）。

（1 分）

完全正确

完全错误

只在 n=1 时成立

渐近意义上正确（ $n \to \infty$ 时），但小 $n$ 时 $O(1)$ 的常数可能很大反而慢——大 O 只描述增长趋势

第 96 题 I10 未作答

关于时间与空间复杂度，错误的是（）。

（1 分）

时间复杂度描述操作次数的增长率

时间与空间复杂度必须相同

常见做法是用空间换时间

空间复杂度描述额外存储空间的增长率

第 97 题 I11 未作答

$O(\log n)$ 的算法中， $n$ 翻倍时操作次数（）。

（1 分）

只增加 $1$ —— $\log(2n) = \log n + \log 2 = \log n + 1$ （以 $2$ 为底）

增加 $n$

翻倍

不变

第 98 题 I12 未作答

一个算法的时间复杂度是 $O(n^2)$ ，另一个是 $O(n \log n)$ ，当 $n = 10^4$ 时大约差多少倍（）。

（1 分）

差不了多少

约 $2$ 倍

约 $\dfrac{n}{\log_2 n} = \dfrac{10^4}{\approx 13} \approx 770$ 倍

约 $5$ 倍

第 99 题 I13 未作答

记忆化搜索与递推的关系，正确的是（）。

（1 分）

递推不需要状态定义

记忆化是贪心的一种

记忆化是自顶向下的 DP、递推是自底向上的 DP——本质等价、复杂度相同

两者只能选其一

第 100 题 I14 未作答

$n = 10^5$ ，下列复杂度中在 $1$ 秒内无法完成的是（）（设 $1$ 秒约 $10^8$ 次运算）。

（1 分）

$O(n \sqrt{n})$ （约 $3.2 \times 10^7$ 次）

$O(n \log n)$ （约 $1.7 \times 10^6$ 次）

$O(n)$ （ $10^5$ 次）

$O(n^2)$ （ $10^{10}$ 次——超出 $10^8$ 上限 $100$ 倍）

拾

真题演练

3 QUESTIONS · 真题演练不计分

第 1 题单选未作答

对于给定的 $n$ ，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。

01int i, j, k = 0;
02for (i = 0; i < n; i++) {
03    for (j = 0; j < n; j *= 2) {
04        k = k + n / 2;
05    }
06}

（0 分）

$O(n)$

$O(n\log n)$

$O(n\sqrt{n})$

$O(n^2)$

CSP-S 2022 · 单选第13题｜知识点排序稳定性、剪枝、逻辑运算

第 2 题单选未作答

以比较为基本运算，在 $n$ 个数的数组中找最大的数，在最坏情况下至少要做（）次运算。

（0 分）

$\frac{n}{2}$

$n-1$

$n$

$n+1$

CSP-S 2022 · 单选第14题｜知识点剪枝、数组越界

第 3 题单选未作答

假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（）

（0 分）

$O(n)$

$O(\log n)$

$O(n \log n)$

$O(1)$

CSP-S 2024 · 单选第2题｜知识点剪枝、排序稳定性

重置作答

专题 S03 复杂度分析 · 复习强化

判 分 报 告

Big O 与渐近记号

循环与代码段分析

递归复杂度

排序复杂度回顾

空间复杂度

记忆化搜索

剪枝优化

分治

综合分析

真 题 演 练

打印

导出 HTML 子卷

判分报告

真题演练