数步骤理解 Big-O
Big-O 描述输入增长时工作量的增长上界，不是依赖设备的毫秒数。本课运行几个小函数，统计关键操作，把 n 从 4 翻倍到 8、16，比较计数，观察四种增长规律。
计数器像里程表，记录做了多少工作，而非花了多久。一次加法、一次探测或一对索引让计数增加一。对本课选定的函数和输入，n 翻倍后：计数不变对应 O(1)，增加一对应 O(log n)，翻倍对应 O(n)，变为四倍对应 O(n²)。这些实验展示已知算法的规律；有限次测量本身不构成任意算法复杂度的证明。
翻倍实验如何工作
每种模式运行一个便于统计主要操作的 Python 函数：
- O(1)：
get_last(arr)读取arr[-1]，直接定位末尾，不遍历数组。 - O(log n)：
find(arr, target)在有序数组上二分查找。目标大于所有元素，走未命中的最坏情况。每次缩小约一半范围，在本课的输入规模下，n翻倍恰好多一次探测。 - O(n)：
total(arr)访问每个元素一次，操作数等于长度。 - O(n²)：
count_pairs(arr)用嵌套循环处理每个(i, j)。画面中边长为n的网格共有n²个单元，边长翻倍，面积变为四倍。
每种测量模式先逐步运行 n = 4，让你看清什么动作增加计数。之后的 n = 8 和 n = 16 压缩为整段扫过，结果加入同一张增长图。三个点配合曲线和翻倍表，展示该函数的增长类别。
第五种模式是竞速（Race）。四个函数都用 n = 16，共享时钟，每个节拍各执行一次操作。get_last 在第 1 拍结束，find 在第 5 拍结束，total 在第 16 拍结束。此时 count_pairs 才完成 256 次操作中的 16 次，还要继续执行。最后的图汇总所有测量，并加入 n·log n 和 2ⁿ 两条虚线参考，比较 O(1) < O(log n) < O(n) < O(n²) < … 的增长顺序。
逐步演示
默认是竞速模式，四条轨道的输入均为 n = 16，每拍各执行一次操作。
- 第 0 拍：开始。 四个函数同时出发，比较谁先结束、谁还在运行。
- 第 1 拍：O(1) 结束。
get_last一次读取最后一个元素，不访问另外十五个。 - 第 2–5 拍：O(log n) 结束。
find每拍缩小范围，第 5 次探测后范围为空。十六个元素共探测五次。 - 第 6–16 拍：O(n) 结束。
total完成十六次访问，恰好n次。count_pairs此时只完成 16／256 次。 - 后续节拍：O(n²) 继续。
count_pairs处理完全部 256 对才结束。在n = 16时，它的操作数是total的 16 倍；n每翻倍，这个比值也翻倍。 - 汇总图。 各轨道的翻倍实验汇入四条测量曲线：O(1) 保持水平，O(n²) 向上增长。
- 增长顺序。 加入
n·log n和2ⁿ参考。前者对应归并排序等算法，增长介于 O(n) 与 O(n²) 之间；后者在足够大的输入下比图中这些多项式函数增长更快。
这个顺序比较增长率。竞速中的结束顺序还依赖本课统一的一操作一节拍模型。要观察某个函数的计数过程，可以切换到对应模式：从 n = 4 开始，再翻倍到 8、16，比较不变、加一、乘二、乘四四种规律。把 O(n) 模式播放到最后，还能看到虚线 2n + 3：斜率和位置变了，仍是线性增长。
为什么复杂度忽略常数
2n + 3 中，每个元素做更多次固定操作，会改变直线斜率；固定的准备和收尾工作会让直线上移。两者都不改变线性增长类别。Big-O 关注输入足够大时的上界，忽略固定倍数和低阶项。
log₂ n 与 log₁₀ n 只差常数倍，因此都属于 O(log n)。本课据此选择每个函数的主要操作来统计：访问、探测或索引对。每次计数背后的其他固定工作归入常数因子。
这不保证小输入上的实际速度。n = 4 时，count_pairs 为 16 次、total 为 4 次；n = 16 时，两者相差 16 倍，这个比值随每次翻倍继续翻倍。固定常数可能改变小输入的比较结果，但无法长期抵消不同的增长阶。
边界情况
- 最坏情况是选定的场景。 本课
find搜索不存在的值。若首次探测就命中，只需一次操作，但最坏情况仍是 O(log n)。 - O(1) 不等于便宜的一次操作。 它表示计数不随
n增长。本课翻倍时计数为 1 → 1 → 1，即使单次操作很贵，也仍是常数级。 - 单独测量使用各自的纵轴。 O(1) 使用紧凑范围，O(n²) 使用更高范围。只有竞速图共享固定刻度，其中
(16, 256)会超出画框，这是预设的展示效果。任何固定高度的图都无法容纳无限增长的二次函数。 - 输入固定为 4 → 8 → 16。 这些值便于比较 ×1、+1、×2、×4，本课因此没有自由输入滑块。
常见错误
- “O(1) 就是快。” 它表示常数级。一项慢但不依赖
n的操作仍是 O(1)，一次很快的全遍历仍是 O(n)。 - 把 2n + 3 和 n 当成不同类别。 常数改变斜率或位置，不改变线性增长。
- 把 n² 理解成做两遍。 两次独立遍历是 2n，属于 O(n)；每次外层遍历都完整执行一次内层遍历，才会形成本课的 n²。
- 统计每条底层指令。 分析本课这些函数时，可统计主导操作，固定的附加工作不会改变增长阶。
- 把增长率当成实际完成时间。 本课竞速使用相同的计数节拍；真实耗时还受单次操作成本和输入规模影响。
本课的简化
计数器只统计各函数的主要操作，不分别统计循环维护、比较和最后打印等指令。实际运行还受缓存、解释器等因素影响，小输入的计时可能偏离图中曲线。本课通过统一计数模型，展示这些函数随输入增长的工作量。