【GESP】C++四级考试大纲知识点梳理, (9) 简单算法复杂度的估算

GESP C++四级官方考试大纲中，共有11条考点，本文针对第9条考点进行分析介绍。

（9）简单算法复杂度的估算，含多项式、指数复杂度。

四级其他考点回顾：

• 【GESP】C++四级考试大纲知识点梳理, (1) 指针
• 【GESP】C++四级考试大纲知识点梳理, (2) 结构体和二维数组
• 【GESP】C++四级考试大纲知识点梳理, (3) 模块化和函数
• 【GESP】C++四级考试大纲知识点梳理, (4) 变量和作用域
• 【GESP】C++四级考试大纲知识点梳理, (5) 值传递
• 【GESP】C++四级考试大纲知识点梳理, (6) 递推算法
• 【GESP】C++四级考试大纲知识点梳理, (7) 排序算法基本概念
• 【GESP】C++四级考试大纲知识点梳理, (8) 冒泡、插入、选择排序

---

一、什么是算法复杂度？

算法复杂度用于衡量算法运行时间或占用空间随输入规模变化的增长速度。

• 时间复杂度：关注算法执行时间。
• 空间复杂度：关注算法占用的内存。

本文重点介绍时间复杂及其估计。

二、常见算法时间复杂度

时间复杂度（Time Complexity）是用来描述算法在输入规模 n 增大时，执行所需基本操作次数的增长速度。

我们用大 $O$ 记号来表示，例如：

• $O(1)$：与输入无关（常数时间）
• $O(n)$：线性增长
• $O(n^2)$：平方增长
• $O(2^n)$：指数增长
• $O(n!)$：阶乘增长

2.1 常见时间复杂度总结对比表

时间复杂度	中文名称	增长速度	示例场景	形象比喻
$O(1)$	常数级	最慢（最优）	访问数组元素、哈希表操作	按电梯：不管上多少层都是按一下
$O(\log n)$	对数级	很慢	二分查找、AVL 树、堆优化	猜数字游戏：每次排除一半范围
$O(n)$	线性级	中等偏慢	遍历数组、线性查找	点名：班级人数翻一倍，时间翻一倍
$O(n \log n)$	线性对数级	比线性略快	快速排序、归并排序、堆排序	整理扑克牌：边分组边排序
$O(n^2)$	二次多项式级	快（效率差）	冒泡、选择、插入排序；邻接矩阵图	发红包：每人给其他所有人发一次
$O(n^k)$	k次多项式	较慢（随k增大而变慢）	k重循环、多维动态规划	魔方：每个维度都要转一遍
$O(2^n)$	指数级	极快（很差）	子集问题、递归斐波那契	细胞分裂：每次都分裂成两个
$O(n!)$	阶乘级	最快（最差）	全排列、旅行商、N 皇后问题	排队照相：所有人排列组合

2.1.1 【特别说明】多项式复杂度

多项式复杂度（Polynomial Time Complexity）是指算法的时间复杂度可以用多项式表示，即：

• 形如 $O(n^k)$，其中 k 为常数
• 常见的有 $O(1)$、$O(n)$、$O(n^2)$、$O(n^3)$ 等
• 特点：随输入规模 n 增长相对平缓
• 一般认为是”可解”的复杂度级别

2.1.2 【特别说明】指数复杂度

指数复杂度（Exponential Time Complexity）是指算法的时间复杂度呈指数增长，即：

• 形如 $O(k^n)$，其中 k 为常数，n 为输入规模
• 常见的有 $O(2^n)$、$O(3^n)$ 等
• 特点：随输入规模 n 增长极快
• 一般认为是”难解”的复杂度级别
• 典型问题如：子集枚举、递归斐波那契等

---

2.2 不同复杂度时间增长速度示意

n	O(1)	O(log n)	O(n)	O(n²)	O(2ⁿ)	O(n!)
5	1	2.3	5	25	32	120
10	1	3.3	10	100	1024	3,628,800
20	1	4.3	20	400	1,048,576	2.43e18
30	1	4.9	30	900	1,073,741,824	2.65e32

✅ 多项式复杂度随着 n 增长是平稳的

❌ 指数/阶乘复杂度很快无法承受，程序跑不动

2.3 根据输入规模选择算法

在实际编程中，需要根据输入规模选择合适的算法。以下是一个简单的参考指南：

输入规模(n)	可接受的时间复杂度	建议算法类型	典型应用场景
n ≤ 10	$O(n!)$、$O(2^n)$	暴力枚举、回溯	小规模全排列、子集生成
n ≤ 20	$O(2^n)$	状态压缩DP、回溯剪枝	旅行商问题、背包问题
n ≤ 100	$O(n^3)$	动态规划、Floyd算法	最短路径、矩阵连乘
n ≤ 1000	$O(n^2)$	简单排序、二重循环	冒泡排序、选择排序
n ≤ 10⁶	$O(n\log n)$	高效排序、分治	快速排序、归并排序
n ≤ 10⁷	$O(n)$	线性扫描、哈希表	数组遍历、字符串匹配
n > 10⁷	$O(\log n)$ 或 $O(1)$	二分查找、数学公式	有序数组查找、常数时间哈希表查找

2.3.1 算法选择注意事项

1. 考虑实际约束
   • 时间限制（通常1-2秒）
   • 内存限制（通常64-256MB）
   • CPU速度（一般1秒可执行10⁸左右基本运算）
2. 权衡取舍
   • 代码实现难度
   • 算法可读性和可维护性
   • 实际运行效率（常数因子）
3. 特殊情况考虑
   • 输入数据特征（如已排序、近似排序）
   • 空间复杂度要求
   • 算法稳定性需求

2.3.2 实践建议

• 小规模数据：优先选择容易实现的算法
• 大规模数据：必须考虑算法效率
• 关键场景：可以牺牲代码简洁性换取性能
• 通用场景：在可接受范围内优先选择可维护性好的方案

---

三、算法复杂度判断一般步骤

判断一个算法的时间复杂度，核心在于分析：随着输入规模 n 增大，算法的基本操作（如加法、比较、赋值）执行次数增长速度如何。

📌 第一步：找出基本操作：

• 通常是最内层循环中重复执行的操作，如加法、比较、递归调用等。

📌 第二步：分析控制结构（顺序/分支/循环/递归）：

• 顺序结构：多个操作的复杂度相加，如 $O(n) + O(n^2)$，根据加法规则只保留最大项 $O(n^2)$
• 条件结构：if-else 分支取时间复杂度较大的那个分支，如 if 分支是 $O(n)$，else 分支是 $O(n^2)$，则取 $O(n^2)$
• 循环结构：分析循环变量的变化规律，如 for(i=0;i<n;i++) 执行 n 次，复杂度为 $O(n)$
• 递归结构：先写出递归方程，如 $T(n) = T(n-1) + 1$，然后求解得到复杂度 $O(n)$

📌 第三步：用渐进符号 $O$ 表示:

• 只保留最高阶项，忽略常数因子和低阶项。例如:
  • $3n^2 + 2n + 1 \rightarrow O(n^2)$
  • $n^3 + 100n^2 \rightarrow O(n^3)$
  • $2^n + n^2 \rightarrow O(2^n)$

---

3.1 举例说明

例1：简单循环

for (int i = 0; i < n; i++) {
    cout << i << endl;
}

• 基本操作：cout 执行 n 次
• 复杂度：$O(n)$（线性复杂度）

---

例2：嵌套循环

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << "," << j << endl;
    }
}

• 外层执行 $n$ 次，内层每次执行 $n$ 次
• 总操作次数：$n × n = n^2$
• 复杂度：$O(n^2)$（二次复杂度）

---

例3：不等长嵌套循环

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        cout << i << "," << j << endl;
    }
}

• $j$ 从 $0$ 到 $i-1 \rightarrow$ 总执行次数为 $1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$
• 复杂度：$O(n^2)$（仍然是平方）

---

例4：对数型复杂度$（log n）$

int i = 1;
while (i < n) {
    i = i * 2;
}

• $i$ 每次乘 2：1 → 2 → 4 → 8 → … → n
• 执行次数 $\approx \log_2(n)$
• 复杂度：$O(log n)$（对数复杂度）

---

例5：递归斐波那契（指数复杂度）

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

• 每次调用都拆成两个子问题
• 形成一棵递归树，总节点约 $2^n$
• 复杂度：$O(2^n)$（指数复杂度）

---

例6：全排列问题（阶乘复杂度）

void permute(string s, int l, int r) {
    if (l == r) {
        cout << s << endl;
    } else {
        for (int i = l; i <= r; i++) {
            swap(s[l], s[i]);
            permute(s, l + 1, r);
            swap(s[l], s[i]);
        }
    }
}

• 每个字符都和第一个字符交换，共 $n$ 次
• 每个字符都和第二个字符交换，共 $n-1$ 次
• 每个字符都和第三个字符交换，共 $n-2$ 次
• 总次数：$n + (n-1) + (n-2) + \cdots + 1 = n(n+1)/2$
• 复杂度：$O(n!)$

---

3.2 常见结构对应复杂度口诀

结构类型	示例	时间复杂度
单层循环	for i = 1 to n	$O(n)$
双层嵌套循环	两层循环遍历	$O(n^2)$
三层嵌套循环	三层循环	$O(n^3)$
对数循环	每次乘/除以 2	$O(\log n)$
对数 + 线性	for i = 1 to n, 里面 log i	$O(n \log n)$
指数递归	每次递归调用生成2个或更多子问题（如斐波那契递归）	$O(2^n)$
阶乘递归	每次生成一个子问题	$O(n!)$

---

四、总结要点

项	内容
🎯 核心	时间复杂度描述算法效率
🔍 多项式复杂度	O(n)、O(n²)、O(n³)… 可接受
🚫 指数复杂度	O(2ⁿ)、O(n!) 不可扩展
📐 估算方法	分析循环/递归结构
🧠 实战建议	根据输入范围选择合适算法

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号