XM02-DAY03-预习
2026-07-23 20:09:11
发布于：广东
📊 算法复杂度与枚举排序 · 课前预习笔记
明天要学的东西叫 “算法复杂度”和“枚举算法” ——说白了就是让程序又快又好地解决问题，以及用 “笨办法” 暴力破解问题！
一、先搞懂：什么是算法？
1. 算法的定义
算法 = 解决问题的方法和步骤
就像做一道菜有菜谱，解决一个问题也有固定的步骤。
2. 同一个问题，不同的算法
比如“排序”这个问题：
- 冒泡排序 ← 一种算法
- 选择排序 ← 另一种算法
- sort 排序 ← 又一种算法
💡 问题：这么多算法，怎么判断哪个好哪个坏？
二、时间复杂度 —— 算法跑得快不快
1. 什么是时间复杂度？
时间复杂度 = 算法运行需要的时间（用“大概执行了多少步”来衡量）
不是用秒来算，而是用 “操作次数” 来算。这样不管电脑快还是慢，都能公平比较。
2. 生活类比
你要从 100 本书里找到《西游记》：
- 方法一：一本一本翻，运气好第1本找到，运气差第100本才找到 → 慢
- 方法二：书是按拼音排序的，直接翻到 X 开头的位置 → 快
3. 常见时间复杂度
| 符号 | 读作 | 速度 | 例子 |
|---|---|---|---|
| O(1) | 常数阶 | 🚀 最快 | 直接取数组第一个元素 |
| O(log n) | 对数阶 | 🚀 很快 | 二分查找 |
| O(n) | 线性阶 | ⚡ 快 | 遍历数组找最大值 |
| O(n log n) | 线性对数阶 | 📈 中等 | sort 排序 |
| O(n²) | 平方阶 | 🐢 慢 | 冒泡排序、选择排序 |
| O(2ⁿ) | 指数阶 | 💀 超慢 | 暴力枚举所有子集 |
4. 怎么看时间复杂度？
// O(1) —— 常数时间，不管数据多大都一步搞定
int x = a[5]; // 直接取第5个元素
// O(n) —— 线性时间，数据多几倍，时间就多几倍
for (int i = 1; i <= n; i++) {
sum += a[i]; // n 个数就循环 n 次
}
// O(n²) —— 平方时间，数据多2倍，时间多4倍
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j]; // n×n 次
}
}
6. 考试/竞赛怎么用？
| 数据规模 n | 允许的复杂度 |
|---|---|
| n ≤ 10 | O(n!) 或 O(2ⁿ) 都行 |
| n ≤ 20 | O(2ⁿ) 勉强行 |
| n ≤ 100 | O(n³) 以内 |
| n ≤ 1000 | O(n²) 以内 |
| n ≤ 10⁵ | O(n log n) 以内 |
| n ≤ 10⁷ | O(n) 以内 |
💡 实际应用：如果 n=10000，O(n²) 就是 1亿次操作，可能会超时！这时候就要用 O(n log n) 或更快的算法。
三、空间复杂度 —— 算法占内存多不多
1. 什么是空间复杂度？
空间复杂度 = 算法运行时占用的内存大小
2. 常见空间复杂度
| 符号 | 说明 | 例子 |
|---|---|---|
| O(1) | 常数空间，不随数据变大而变大 | 只用几个变量 |
| O(n) | 线性空间，数据多几倍，内存多几倍 | 开一个大小为 n 的数组 |
| O(n²) | 平方空间 | 开一个 n×n 的二维数组 |
3. 空间换时间（常见技巧）
有时候可以用更多的内存来换更快的速度：
// 桶排序：用 O(n) 的空间，换 O(n) 的时间
int bucket[1005] = {0}; // 多开一个数组（空间↑）
for (...) bucket[x]++; // 排序超快（时间↓）
💡 大部分情况下，时间比空间更宝贵。内存现在很便宜，但时间超时就凉了。
四、枚举算法 —— “笨办法”暴力破解
1. 什么是枚举？
枚举 = 把所有可能的情况都试一遍
就像猜密码时，从 0000 试到 9999，总有一个是对的。虽然笨，但一定能找到答案！
2. 生活类比
你丢了钥匙，不知道掉哪儿了。枚举法就是把每一个可能的地方都找一遍，虽然累，但肯定能找到！
3. 枚举的三大步骤
| 步骤 | 说明 |
|---|---|
| ① 确定范围 | 所有可能的情况是什么？从哪到哪？ |
| ② 逐个验证 | 对每种情况检查一下是否满足条件 |
| ③ 输出答案 | 找到满足条件的就输出 |
4. 枚举经典例题：百元买百鸡
题目：公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只。用 100 元买 100 只鸡，每种鸡至少一只，有几种买法？
思路：暴力枚举所有可能！
#include <iostream>
using namespace std;
int main() {
int count = 0;
// 枚举公鸡数量：1~20（100元最多买20只公鸡）
for (int x = 1; x <= 20; x++) {
// 枚举母鸡数量：1~33（100元最多买33只母鸡）
for (int y = 1; y <= 33; y++) {
int z = 100 - x - y; // 小鸡数量 = 总数 - 公鸡 - 母鸡
// 检查：小鸡数量要≥1，且价格正好100元
if (z >= 1 && 5*x + 3*y + z/3.0 == 100) {
cout << "公鸡" << x << "只，母鸡" << y << "只，小鸡" << z << "只" << endl;
count++;
}
}
}
cout << "共有" << count << "种买法" << endl;
return 0;
}
5. 枚举的优缺点
| 优点 | 缺点 |
|---|---|
| ✅ 简单直接，容易想 | ❌ 可能非常慢（数据大时） |
| ✅ 一定能找到答案 | ❌ 需要先确定范围 |
| ✅ 不容易出错 | ❌ 范围太大时跑不动 |
💡 记住：枚举就是 “暴力出奇迹” ，当你想不到好方法时，先试试枚举！
五、冒泡排序（复习巩固）
1. 核心思想
相邻比较，大的往后冒，每轮把最大的“冒”到最后面。
for (int i = 1; i <= n - 1; i++) {
for (int j = 1; j <= n - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}
2. 时间复杂度：O(n²)
- 外层循环 n-1 次
- 内层循环 n-i 次
- 总次数 ≈ n²/2 → O(n²)
3. 优化版（加标记提前结束）
for (int i = 1; i <= n - 1; i++) {
bool flag = false;
for (int j = 1; j <= n - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
flag = true;
}
}
if (!flag) break; // 没交换说明已经排好了！
}
六、选择排序（复习巩固）
1. 核心思想
每轮选最小的，放到最前面，像打牌时整理手牌。
for (int i = 1; i <= n - 1; i++) {
int minPos = i;
for (int j = i + 1; j <= n; j++) {
if (a[j] < a[minPos]) {
minPos = j;
}
}
if (minPos != i) {
swap(a[i], a[minPos]);
}
}
2. 时间复杂度：O(n²)
- 外层循环 n-1 次
- 内层循环 n-i 次
- 总次数 ≈ n²/2 → O(n²)
3. 特点
| 对比 | 冒泡排序 | 选择排序 |
|---|---|---|
| 交换次数 | 多（最多 n²/2） | 少（最多 n-1 次） |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 |
| 代码复杂度 | 差不多 | 差不多 |
📝 快速记忆卡
| 概念 | 一句话总结 |
|---|---|
| 时间复杂度 | 算法跑得快不快（操作次数） |
| 空间复杂度 | 算法占内存多不多 |
| O(1) | 最快，数据多大都一样快 |
| O(n) | 快，数据多几倍时间多几倍 |
| O(n²) | 慢，数据多2倍时间多4倍 |
| 枚举算法 | 把所有可能都试一遍 |
| 冒泡排序 | 相邻比较，大的往后冒，O(n²) |
| 选择排序 | 每轮选最小的放前面，O(n²) |
🔥 预习小任务
- 如果 n=1000，O(n²) 的算法大概要执行多少次？如果电脑每秒能执行 1亿次，会超时吗？
- 百元买百鸡问题中，如果不用枚举，还有其他方法吗？
- 冒泡排序和选择排序，哪个的交换次数更少？为什么？
明天上课带着这些问题来，效果翻倍！🚀
全部评论 12
☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺☺
2026-07-23 来自 广东
3
有帮助，赞一个