课程信息
B2.4 · 算法效率 · 已学习

大 O 表示法

使用课堂讲义与教材第 358–361 页复习大 O 表示法。比较时间与辅助空间如何随输入规模增长。

2026 年 9 月 17 日 · 55 分钟

本节课资源

打开学生讲义（PDF）（英文文件） 课堂活动 ↓ 在 Python 中尝试示例 → 作业 · 截止日期：2026 年 9 月 18 日
动画： 常数增长 · O(1)线性增长 · O(n)对数增长 · O(log n)平方增长 · O(n²)辅助空间
Python · 逐步执行

线性增长 · O(n)

观察输入规模变化时，标记操作次数如何变化。

选择“播放”或“下一行”，跟踪 Python 的执行过程。

Python 实现

高亮表示下一条将执行的语句。数值显示执行该行之前的状态。

visits = []def growth_linear(n):    for i in range(n):        visits.append(i)    return len(visits)

visits 是仅用于显示工作量的记录列表。判断算法本身的辅助空间时，不应计入这些显示日志。我们统计 append 事件，而非每一步 Python 操作。

Python · 逐步执行

辅助空间

比较持续累加的总和与不断增长的输入副本。

选择“播放”或“下一行”，跟踪 Python 的执行过程。

Python 实现

高亮表示下一条将执行的语句。数值显示执行该行之前的状态。

def auxiliary_space(items, copy_input):    total = 0    working = []    for value in items:        total = total + value        if copy_input:            working.append(value)    return total

给定列表占用的是输入空间。在课堂模型中，total 和 value 占用固定数量的存储位置，而副本会增长到 n 个元素。不创建副本时，辅助空间为 O(1)；创建副本时为 O(n)。两种遍历的时间复杂度均为 O(n)。

学完本节课后

  • 区分输入规模与操作次数。
  • 比较常见增长模式，不依赖某台计算机的具体速度。
  • 解释为什么常数因子不会改变大 O 类别。

按自己的节奏通过这些活动复习主题。时长仅供参考。

复习课程

01 · 5 分钟

从比较开始

比较读取列表第一个元素与检查所有元素。列表长度加倍时，什么会发生变化？

02 · 15 分钟

统计操作次数

统计遍历 n 个值的单个循环、两个连续循环，以及两个嵌套循环的工作量。先尝试 n = 4 和 n = 8，再归纳规律。

03 · 15 分钟

描述增长

将常数、对数、线性与平方增长联系到学过的算法。区分增长率与测量得到的执行时间。

04 · 15 分钟

应用表示法

比较线性搜索与二分搜索。说明所考虑的情况，解释有序输入的作用。将辅助空间与时间分开讨论。

05 · 5 分钟

解释

解释为什么完整遍历列表两次仍是线性增长，而不是平方增长。

下课前

离堂问题

输入规模加倍时，线性算法与平方复杂度算法的工作量分别如何变化？

本主题作业

截止日期：2026 年 9 月 18 日 · 4 页 · 已布置

阅读第 358–361 页：大 O 表示法

阅读 Baumgarten、Ganea 与 Turland 编写的《Computer Science for the IB Diploma》第 358–361 页，复习大 O 课程。下一主题：二分搜索。