> **GESP等级：四级 | 考级考点：GESP Python 四级**

# 第16节：算法复杂度——谁跑得更快？

---

## 一、课程概览

| 项目 | 内容 |
|------|------|
| 课程名称 | 算法复杂度——比比谁更快 |
| 课程时长 | 60分钟 |
| 教学形式 | 故事导入（跑步比赛）+ 身体动作模拟 + turtle曲线图 + 动手实验 |
| 核心目标 | 理解时间复杂度的概念，能区分O(1)、O(n)、O(n²)、O(log n) |

### 教学目标

| 维度 | 目标描述 |
|------|----------|
| 知识目标 | 理解时间复杂度的含义，认识四种常见复杂度 |
| 技能目标 | 能分析简单算法的时间复杂度，对比不同排序的速度 |
| 思维目标 | 建立"算法效率"的思维，明白"快"和"慢"是相对的 |
| 情感目标 | 感受算法效率的重要性，学会选择更优的算法 |

### 教学重点与难点

| 类型 | 内容 |
|------|------|
| 重点 | O(1)、O(n)、O(n²)、O(log n)的含义和区别 |
| 难点 | 理解为什么去掉常数和低次项 |
| 易错点 | 混淆O(n)和O(n²)；认为O(1)就是1秒 |

---

## 二、教学准备

### 教具准备
1. 电脑+Python环境（已安装turtle库）
2. 投影仪/大屏幕（展示复杂度曲线图）
3. 跑步比赛道具（计时器）
4. 一张大纸（画坐标轴用）
5. 卡片：O(1)、O(n)、O(n²)、O(log n)四张
6. 折纸（演示二分查找的对数）

### 课前准备
- 测试复杂度曲线绘制代码
- 准备不同数据量的排序对比实验结果
- 准备折纸道具（对半折演示log n）
- 打印复杂度对比图

---

## 三、教学过程（60分钟）

---

### 第一部分：导入环节（10分钟）——谁跑得更快？

#### 1.1 故事：跑步比赛（3分钟）

**老师讲故事**：

"同学们！今天我们学校要举行跑步比赛了！"
"有4个选手参加比赛："

| 选手 | 名字 | 特点 |
|:----:|:----:|:----:|
| 🏃 选手A | 闪电侠 | 一步到位，瞬间到达 |
| 🏃 选手B | 稳步哥 | 一步一步，稳扎稳打 |
| 🏃 选手C | 绕圈王 | 跑一圈又一圈 |
| 🏃 选手D | 对半侠 | 每次砍掉一半距离 |

"比赛距离从10米到1000米，来看看谁更快！"

| 距离 | 闪电侠(O(1)) | 稳步哥(O(n)) | 绕圈王(O(n²)) | 对半侠(O(log n)) |
|:----:|:-----------:|:-----------:|:------------:|:--------------:|
| 10米 | 1步 | 10步 | 100步 | 4步 |
| 100米 | 1步 | 100步 | 10000步 | 7步 |
| 1000米 | 1步 | 1000步 | 1000000步 | 10步 |

"当距离越来越大时——"
"闪电侠总是1步！"
"对半侠只多了几步！"
"稳步哥跟着距离增加！"
"绕圈王...哎呀，他跑得越来越慢了！"

**提问**：
- "距离变成100倍，闪电侠需要多跑几步？"（0步）
- "距离变成100倍，对半侠需要多跑几步？"（只多3步）
- "距离变成100倍，绕圈王需要多跑多少步？"（10000倍！）

#### 1.2 身体游戏（5分钟）

**游戏1：O(1)——拍手一下**
"闪电侠做事一步到位！我们来拍一下手——啪！"
"这就是O(1)——不管数据有多少，一下就搞定！"

> **身体锚点**：打响指或拍手，表示"瞬间完成"

**游戏2：O(n)——在教室里走一圈**
"稳步哥做事是一步一步来的。"
"老师拍手，每拍一下走一步。拍n下，走n步。"
"来，我们一起从教室最左边走到最右边——"
"走得越多，步数越多！"

> **身体锚点**：在原地一步步走，边走边数

**游戏3：O(n²)——原地转圈圈**
"绕圈王做事要绕圈圈！"
"每处理一个数，就要跟其他所有数比一次。"
"100个数，每1个数要跟其他99个比——99×100/2 ≈ 4950次！"

"来，我们做动作：双手画大圈，嘴里念'一圈一圈又一圈'"
"念得越快，圈越多，越累！"

> **身体锚点**：双手画大圈，做转圈动作

**游戏4：O(log n)——折纸游戏**
"对半侠有绝招——每次砍掉一半！"
"拿出一张纸，对折——还剩一半！"
"再对折——还剩四分之一！"
"再对折——还剩八分之一！"

"一张纸对折几次能变成1厘米厚？"
"100页的书，对半找一页需要找几次？"
"答案是log₂(100)≈7次！比100次快多了！"

> **身体锚点**：双手做"对折"动作

#### 1.3 引出主题（2分钟）

"刚才我们做的4个游戏，就代表了4种时间复杂度！"

| 动作 | 时间复杂度 | 含义 |
|:----:|:----------:|:----:|
| 拍一下手 | O(1) | 常数时间 |
| 一步步走 | O(n) | 线性时间 |
| 绕圈圈 | O(n²) | 平方时间 |
| 对折纸 | O(log n) | 对数时间 |

---

### 第二部分：知识点讲解（20分钟）

---

#### 2.1 什么是时间复杂度？（3分钟）

**定义**：

> **时间复杂度 = 算法运行需要的时间（用操作的次数来衡量）**

**注意**：
- 不是用秒来算时间（不同电脑速度不同）
- 而是用"做了多少次操作"来算
- 操作越多，时间越长

**比喻**：
"时间复杂度就像你做作业需要做多少道题——"
"如果老师布置了10道题，你需要做10道（O(n)）"
"如果老师布置了10道题，每道题还有10个小问，你就需要做100道（O(n²)）"

#### 2.2 四种常见复杂度详解（10分钟）

##### O(1)——常数时间

**含义**：不管数据有多少，都只需要1步（或常数步）

**生活中的例子**：
- 翻开字典的第1页（不管字典多厚，翻第1页都是1步）
- 吃盘子里第一个菜（不管有多少菜，吃第一口都是1口）
- 按电梯1楼按钮（不管楼多高，按1楼都是一个动作）

**编程中的例子**：
```python
# O(1) —— 直接拿第一个元素
def get_first(arr):
    return arr[0]

# O(1) —— 数组长度
def get_length(arr):
    return len(arr)
```

**口诀**："O(1)神速一步到，再多数据也不怕"

##### O(n)——线性时间

**含义**：有n个数据，就需要n步操作

**生活中的例子**：
- 全班点名——有50人点50次，有100人点100次
- 找东西——在抽屉里一个个翻，翻完n个抽屉找到
- 排队——排了n个人，需要等n个人

**编程中的例子**：
```python
# O(n) —— 找最大值（需要把所有数看一遍）
def find_max(arr):
    max_val = arr[0]
    for num in arr:  # 循环n次
        if num > max_val:
            max_val = num
    return max_val

# O(n) —— 打印所有元素
def print_all(arr):
    for num in arr:  # 循环n次
        print(num)
```

**口诀**："O(n)稳步一步步，数据多少走多少"

##### O(n²)——平方时间

**含义**：有n个数据，需要做n×n次操作

**生活中的例子**：
- 全班每个人跟其他所有人握手——50人握2500次
- 画一张表——n行n列，共n×n个格子
- 每个同学检查所有同学的作业——n个人，每人看n份

**编程中的例子**：
```python
# O(n²) —— 冒泡排序
def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):          # n次
        for j in range(n-1-i):    # n次
            if arr[j] > arr[j+1]:  # 总共比较 n×(n-1)/2 ≈ n²/2 次
                arr[j], arr[j+1] = arr[j+1], arr[j]

# O(n²) —— 打印乘法表
def print_multiplication_table(n):
    for i in range(1, n+1):    # n次
        for j in range(1, n+1):  # n次
            print(f"{i}×{j}={i*j}", end="\t")
        print()
```

**口诀**："O(n²)慢如蜗牛爬，数据翻倍它翻平方"

##### O(log n)——对数时间

**含义**：每次操作都能砍掉一半数据，只需要log₂(n)步

**生活中的例子**：
- 猜数字游戏：在1-100中猜一个数，每次说"大了"或"小了"
  - 最差需要猜100次吗？不！7次就够了！
  - 因为每次都能排除一半！
- 查字典：翻到中间，看要找的字在前一半还是后一半
  - 1000页的字典，最多查10次！

**为什么叫"log"？**
"log₂(8) = 3" 意思就是"8对半砍3次变成1"
"log₂(16) = 4"
"log₂(100) ≈ 7"
"log₂(1000) ≈ 10"
"log₂(10000) ≈ 14"

**编程中的例子**：
```python
# O(log n) —— 二分查找
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:      # 每次砍掉一半
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1    # 砍掉左半
        else:
            right = mid - 1   # 砍掉右半
    return -1
```

**口诀**："O(log n)对半找，数据翻倍它只加1"

#### 2.3 复杂度对比（3分钟）

| 数据量n | O(1) | O(log n) | O(n) | O(n²) |
|:-------:|:----:|:--------:|:----:|:-----:|
| 10 | 1 | ~3 | 10 | 100 |
| 100 | 1 | ~7 | 100 | 10,000 |
| 1,000 | 1 | ~10 | 1,000 | 1,000,000 |
| 10,000 | 1 | ~14 | 10,000 | 100,000,000 |
| 100,000 | 1 | ~17 | 100,000 | 10,000,000,000 |

**观察**：
- n=100时：O(n²)比O(n)慢100倍
- n=1000时：O(n²)比O(n)慢1000倍
- n越大，O(n²)越慢得可怕！

**板书画图**：
```
操作次数
  ↑
  |                  O(n²) ↗
  |                      ↗
  |                  ↗
  |               O(n) ↗
  |                 ↗
  |            ↗
  |        ↗  O(log n)
  |    ↗
  |  O(1)  ——————————————→
  +——————————————→ 数据量n
```

#### 2.4 三种排序的时间复杂度（2分钟）

**回顾我们学过的三种排序**：

| 排序方法 | 时间复杂度 | 解释 |
|:--------:|:----------:|:----:|
| 冒泡排序 | O(n²) | 两层循环，n×(n-1)/2次比较 |
| 选择排序 | O(n²) | 两层循环，找最小值n-1轮 |
| 插入排序 | O(n²) | 最坏情况n×(n-1)/2次比较 |

**但是插入排序有特殊情况！**
- 最好情况（数据已经排好）：只需要O(n)
- 因为每个元素只需要跟前面一个比较就停了

**所以**：
- 数据基本有序 → 插入排序最快！
- 数据完全随机 → 冒泡和选择差不多
- 数据完全逆序 → 三个都很慢

#### 2.5 为什么要"去掉常数和低次项"？（2分钟）

**问题**：为什么O(2n+100) 简写成 O(n)？

**比喻**：
"你家有1亿块钱，我多给你100块，你在意吗？"
"不在意！因为100块相对于1亿块来说太少了！"

**同样道理**：
- 当n很大时，常数项和低次项的影响可以忽略不计
- 比如 n² + 100n，当n=10000时：
  - n² = 100,000,000
  - 100n = 1,000,000
  - 100n 只有 n² 的 1%
- 所以 n² + 100n → 只看最高次 → O(n²)

**规则**：
1. **去掉常数**：O(2n) → O(n)
2. **去掉低次项**：O(n²+n) → O(n²)
3. **只保留最高次项**

**练习题**：
- O(3n+5) = O(___)
- O(n²+1000n) = O(___)
- O(5n²+2n+100) = O(___)
- O(10) = O(___)

> **答案**：O(n), O(n²), O(n²), O(1)

---

### 第三部分：演示环节（10分钟）——turtle复杂度曲线图

#### 3.1 画复杂度对比曲线（5分钟）

**老师操作**：
1. 运行turtle复杂度曲线代码
2. 屏幕上画出坐标轴——横轴是n，纵轴是操作次数
3. 依次画出O(1)、O(log n)、O(n)、O(n²)的曲线

**引导观察**：
- "看！O(1)是一条直线——永远不变"
- "O(log n)刚开始涨得快，后来越来越平缓"
- "O(n)是一条斜线——稳步上升"
- "O(n²)弯得像火箭——越到后面涨得越快！"

#### 3.2 排序速度实测（3分钟）

**老师用代码实际测试**：

```python
import time
import random

# 生成不同大小的数据
sizes = [10, 50, 100, 200, 500]

for size in sizes:
    data = [random.randint(1, 1000) for _ in range(size)]

    # 测试冒泡排序
    d = data.copy()
    start = time.time()
    bubble_sort(d)  # 假设有bubble_sort函数
    bubble_time = time.time() - start

    print(f"n={size}: 冒泡排序={bubble_time:.4f}秒")
```

**展示结果**，让学生看到：
- n=10时：几乎瞬间完成
- n=100时：还能接受
- n=500时：明显变慢
- n=1000时：非常慢

#### 3.3 可视化对比（2分钟）

用柱状图展示不同数据量下各种排序的速度，直观感受O(n²)的"恐怖"。

---

### 第四部分：实操环节（15分钟）

#### 4.1 任务1：运行复杂度曲线代码（3分钟）

1. 打开 `04_算法复杂度.py` 文件
2. 运行代码，看到复杂度曲线图
3. 观察四条曲线的形状差异

#### 4.2 任务2：填空分析复杂度（4分钟）

分析下面的代码，填出时间复杂度：

```python
# 代码1
def sum_list(arr):
    total = 0
    for num in arr:        # 循环n次
        total += num
    return total
# 时间复杂度：O(____)

# 代码2
def print_pairs(arr):
    n = len(arr)
    for i in range(n):     # 循环n次
        for j in range(n):  # 循环n次
            print(arr[i], arr[j])
# 时间复杂度：O(____)

# 代码3
def get_mid(arr):
    mid = len(arr) // 2    # 一步
    return arr[mid]         # 一步
# 时间复杂度：O(____)

# 代码4
def find_in_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:    # 每次砍掉一半
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
# 时间复杂度：O(____)
```

#### 4.3 任务3：排序速度对比实验（5分钟）

写一个程序对比三种排序在不同数据量下的速度：

```python
import time
import random

def compare_sorts():
    """对比三种排序的速度"""
    sizes = [10, 50, 100, 200]

    print(f"{'n':>5} | {'冒泡排序':>10} | {'选择排序':>10} | {'插入排序':>10}")
    print("-" * 45)

    for size in sizes:
        # 生成随机数据
        data = [random.randint(1, 1000) for _ in range(size)]

        # 分别测试三种排序（需要先写排序函数）
        # ...

    print("\n结论：_________________________________")
```

**思考**：
- 当n=10时，哪种排序最快？
- 当n=200时，差距有多大？
- 为什么插入排序有时比冒泡快？

#### 4.4 任务4：优化意识（3分钟）

**讨论**："如果处理100万个数据，你能用冒泡排序吗？"

答案是：不能！因为100万² = 1万亿次操作，太慢了！

**那怎么办？**
1. 用更快的排序算法（比如快速排序、归并排序，O(n log n)）
2. 用二分查找代替线性查找（O(log n) vs O(n)）
3. 用哈希表代替列表查找（O(1) vs O(n)）

---

### 第五部分：小测环节（5分钟）

#### 5.1 连线题

把左边的复杂度名称连到右边的含义：

| 复杂度 | 含义 |
|:------:|:----:|
| O(1) | 对半砍，对数时间 |
| O(n) | 常数时间，一步到位 |
| O(n²) | 线性时间，逐个操作 |
| O(log n) | 平方时间，双重循环 |

#### 5.2 选择题（2题）

**第1题**：以下哪个复杂度表示"数据翻倍，操作次数也翻倍"？
- A. O(1)
- B. O(n) ✅
- C. O(n²)
- D. O(log n)

**第2题**：n=100时，O(n²)大约需要多少次操作？
- A. 100次
- B. 1000次
- C. 10000次 ✅
- D. 1000000次

#### 5.3 判断题（2题）

**第3题**：冒泡排序的时间复杂度是O(n²)。（✅）

**第4题**：O(2n+100)可以简化成O(n)。（✅）

#### 5.4 排序题

**第5题**：将以下复杂度按"从快到慢"排序：
O(n²), O(1), O(n), O(log n)

> **答案**：O(1) → O(log n) → O(n) → O(n²)（从快到慢）

---

## 四、课后延伸

### 复杂度在日常生活中的应用
- 收拾书包：直接拿书(O(1)) vs 一本本翻(O(n))
- 在图书馆找书：按分类找(O(log n)) vs 一本本找(O(n))
- 整理房间：排好所有东西(O(n²)) vs 随手放好(O(1))

### 更多复杂度
- O(n log n)：快速排序、归并排序——比O(n²)快得多！
- O(n³)：三层循环——更慢！
- O(2ⁿ)：指数时间——非常非常慢！

### 课程总结回顾
"今天是我们这个阶段最后一节课。我们来回顾一下——"

**四种课学到的内容**：
1. 冒泡排序——气泡往上冒
2. 选择排序和插入排序——选秀和摸牌
3. 递推算法——从已知推未知
4. 算法复杂度——比谁更快

---

## 五、板书设计

```
╔══════════════════════════════════════════════╗
║        算 法 复 杂 度 —— 谁更快？            ║
║                                              ║
║  时间复杂度 = 操作次数                       ║
║                                              ║
║  四种复杂度：                                 ║
║                                              ║
║  O(1)  常数时间   一步到位   ⚡              ║
║  O(log n) 对数时间  对半找  🔍              ║
║  O(n)  线性时间   逐个操作   🚶              ║
║  O(n²) 平方时间   两两比较   🌀              ║
║                                              ║
║  速度排名：O(1) > O(log n) > O(n) > O(n²)   ║
║                                              ║
║  简化规则：                                   ║
║  ① 去掉常数：O(2n) → O(n)                    ║
║  ② 去掉低次：O(n²+n) → O(n²)                 ║
║  ③ 只看最高次                                ║
║                                              ║
║  口诀：                                       ║
║  一次常数O1，线性On，平方On2，对数Ologn      ║
║  O(1)神速一步到                               ║
║  O(n)稳步一步步                               ║
║  O(n²)慢如蜗牛爬                              ║
║  O(log n)对半找                              ║
╚══════════════════════════════════════════════╝
```

---

## 六、课程反思

### 教师自评要点
1. 孩子是否理解"时间复杂度不是实际时间，而是操作次数"？
2. 身体动作模拟是否有效帮助记忆？
3. 曲线图演示是否直观？
4. 能否区分O(1)、O(n)、O(n²)？
5. 是否理解优化算法的重要性？

### 常见问题应对
- **孩子问"O(log n)的log是什么意思"**：用折纸解释——对折几次变成1？（如果不懂对数，就说"对半砍的次数"）
- **孩子不理解为什么去掉常数**：用"一大箱苹果加一个苹果"来比喻
- **孩子觉得O(1)无聊**：强调"O(1)是最快的！是很多算法追求的目标！"

### 课程总结

这是阶段20的最后一节课，建议做一个小总结：

1. **复习四节课的核心内容**：
   - 冒泡排序：相邻比较，大的往后
   - 选择排序：找最小的放前面
   - 插入排序：插入已排好序列
   - 递推：从已知推未知
   - 复杂度：算法效率的量尺

2. **鼓励继续学习**：
   "你们已经学会了排序、递推和算法分析，这些都是编程里非常重要的知识！"
   "下一阶段，我们会学到更多有趣的东西——比如查找、递归、动态规划..."

3. **颁发"小算法家"证书**（如有准备）