Day 029 — 算法入门：图解
时间复杂度对比、排序算法过程、搜索算法过程的图解
1️⃣ 时间复杂度增长趋势
操作数
↑
│ O(n!) ★
│ ★
│ O(2ⁿ) ★
│ ★
│ O(n²) ★
│ ★
│ O(n log n) ★
│ ★
│ O(n) ★
│ ★
│ O(log n) ★
│ _★_____
│ ★
│ ★
│★_________________________→ 输入规模 n
★ — 操作数随着 n 增长
2️⃣ 常见复杂度对比表 (n=1000)
算法 复杂度 操作数(≈)
────────────────────────────────────
常数时间 O(1) 1
哈希查找 O(1) 1
二分查找 O(log n) 10
线性查找 O(n) 1,000
归并排序 O(n log n) 9,966
选择排序 O(n²) 1,000,000
指数时间 O(2ⁿ) 1.07×10³⁰¹
1000万 ┤ ┌───
┤ ██
100万 ┤ ██ 选择/冒泡 O(n²)
┤ ██
10万 ┤ ██
┤ ██
1万 ┤██
┤█
1000 ┤█─────── 归并/快速 O(n log n)
█
100 ┤█───── 二分 O(log n)
10 ┤█───
1 ┤█─
└────────────────────
10 100 1000
结论: 数据规模越大，好的算法优势越明显！
3️⃣ 冒泡排序过程
原始: [5, 3, 8, 6, 4]
第1趟:
5 vs 3 → 交换 [3, 5, 8, 6, 4]
5 vs 8 → 不动 [3, 5, 8, 6, 4]
8 vs 6 → 交换 [3, 5, 6, 8, 4]
8 vs 4 → 交换 [3, 5, 6, 4, 8] ← 8 冒泡到位
第2趟:
3 vs 5 → 不动 [3, 5, 6, 4, 8]
5 vs 6 → 不动 [3, 5, 6, 4, 8]
6 vs 4 → 交换 [3, 5, 4, 6, 8] ← 6 冒泡到位
第3趟:
3 vs 5 → 不动 [3, 5, 4, 6, 8]
5 vs 4 → 交换 [3, 4, 5, 6, 8] ← 5 冒泡到位
第4趟:
3 vs 4 → 不动 [3, 4, 5, 6, 8] ← 全部有序
4️⃣ 选择排序过程
原始: [5 | 3, 8, 6, 4]
↑已排序 ↑未排序区
第1趟: 找未排序最小值 3
[3 | 5, 8, 6, 4] ← 3 与 5 交换
第2趟: 找未排序最小值 4
[3, 4 | 8, 6, 5] ← 4 与 5 交换
第3趟: 找未排序最小值 5
[3, 4, 5 | 6, 8] ← 5 与 8 交换
第4趟: 找未排序最小值 6
[3, 4, 5, 6 | 8] ← 不动
5️⃣ 插入排序过程
初始: [5 | 3, 8, 6, 4]
↑已排序 ↑未排序
第1步: 拿出 3, 与 5 比较
[5, 5, 8, 6, 4] → 5 > 3, 右移
[3, 5, 8, 6, 4] → 插入 3
第2步: 拿出 8, 与 5 比较
[3, 5, 8, 6, 4] → 8 > 5, 不动
第3步: 拿出 6, 与 8 比较
[3, 5, 8, 8, 4] → 8 > 6, 右移
[3, 5, 6, 8, 4] → 插入 6
第4步: 拿出 4, 与 8 比较
[3, 5, 6, 8, 8] → 8 > 4, 右移
[3, 5, 6, 6, 8] → 6 > 4, 右移
[3, 5, 5, 6, 8] → 5 > 4, 右移
[3, 4, 5, 6, 8] → 插入 4
6️⃣ 快速排序过程
递归树:
[3,7,8,5,2,1,9,5,4]
│ pivot=5
┌───────┴───────┐
│ │
[3,2,1,4] [7,8,9,5]
│ │
pivot=2 pivot=8
┌───┴───┐ ┌───┴───┐
│ │ │ │
[1] [3,4] [7,5] [9]
│ │
pivot=3 pivot=5
┌───┐ ┌───┐
│ │ │ │
[] [4] [5] [7]
合并:
[1,2,3,4] [5,7,8,9]
\ /
[1,2,3,4,5,5,7,8,9] ← 注意两个 5
7️⃣ 归并排序过程
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43, 3] [9, 82, 10]
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
/ \ / \ / \ |
[38] [27] [43] [3] [9] [82] [10]
\ / \ / \ / |
[27,38] [3,43] [9,82] [10]
\ / \ /
[3, 27, 38, 43] [9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82]
合并两个有序数组
合并 [27, 38] 和 [3, 43]:
队列一: [27, 38] 队列二: [3, 43]
│ │
└─────── 27 vs 3 ──────┘
3 < 27 → 取 3 ✅
队列一: [27, 38] 队列二: [43]
│ │
└─────── 27 vs 43 ─────┘
27 < 43 → 取 27 ✅
队列一: [38] 队列二: [43]
│ │
└─────── 38 vs 43 ─────┘
38 < 43 → 取 38 ✅
队列一: [] 队列二: [43]
→ 直接追加剩余 43 ✅
结果: [3, 27, 38, 43]
8️⃣ 二分搜索过程
数组: [1, 3, 4, 6, 7, 8, 9, 12]
目标: 9
第一步:
[1, 3, 4, 6, 7, 8, 9, 12]
L=0 mid=3 R=7
arr[3]=6 < 9 → 搜索右半部分
第二步:
[7, 8, 9, 12]
L=4 mid=5 R=7
arr[5]=8 < 9 → 搜索右半部分
第三步:
[9, 12]
L=6 mid=6 R=7
arr[6]=9 == 9 ✅ 找到!
9️⃣ 各算法对比
稳定 原地 时间(平均) 时间(最坏) 空间
────────────────────────────────────────
冒泡 ✅ ✅ O(n²) O(n²) O(1)
选择 ❌ ✅ O(n²) O(n²) O(1)
插入 ✅ ✅ O(n²) O(n²) O(1)
快速 ❌ ✅ O(n log n) O(n²) O(log n)
归并 ✅ ❌ O(n log n) O(n log n) O(n)
Timsort ✅ ✅ O(n log n) O(n log n) O(n) ← Python 内置
🔟 搜索算法对比
数据规模 线性搜索 二分搜索
──────────────────────────────────────
n=100 ~100 次比较 ~7 次比较
n=1,000 ~1,000 次比较 ~10 次比较
n=10,000 ~10,000 次比较 ~14 次比较
n=100,000 ~100,000 次比较 ~17 次比较
n=1,000,000 ~1M 次比较 ~20 次比较
结论: 数据越大，二分搜索优势越明显！