C / C++ / 系统课时

用大 O 表示算法增长速度

用大 O 表示算法增长速度

比较算法时,单次运行耗时很容易受到 CPU、编译器和输入内容影响。大 O 关注的是数据规模不断增大时,操作数量如何增长,因此更适合判断算法在小数据与大数据下是否仍然可接受。

学习目标

  • 理解大 O 描述的是随数据规模变化的增长趋势
  • 区分 O(1)、O(log n)、O(n) 和 O(n²) 的增长差异
  • 能根据数据规模判断复杂度差异何时开始产生明显影响

大 O 关注增长趋势

设输入规模为 n。一次固定次数的操作,无论 n 多大都不明显增加工作量,可以记为 O(1);如果工作量与 n 大致成正比,就是 O(n);如果每次操作都能把待处理范围缩小一大部分,常见 O(log n);如果需要对大量元素两两组合处理,则经常出现 O(n²)。

大 O 会忽略常数和低阶项。例如执行次数为 3n + 20,当 n 足够大时,增长主要由 n 决定,因此通常记为 O(n),而不是把固定的 3 和 20 保留下来。

常见复杂度增长有多大差异

下面用近似操作次数观察几种增长速度。O(log n) 一列按以 2 为底的对数向上取整,只用于帮助建立直觉;在大 O 分析中,对数底数通常不会改变复杂度类别。

数据规模 n O(1) O(log n) O(n) O(n²)
10 1 4 10 100
100 1 7 100 10000
1000 1 10 1000 1000000

当 n 从 100 增加到 1000 时,O(n) 的操作量大约扩大 10 倍,而 O(n²) 会扩大约 100 倍。O(log n) 的增长则非常缓慢,这也是很多搜索与树结构算法努力缩小问题范围的原因。

常见大 O 复杂度增长曲线

不要把复杂度当成精确耗时

O(n) 并不表示处理 n 个元素一定执行恰好 n 条机器指令,O(1) 也不表示只执行一条指令。它描述的是规模变化后工作量的数量级趋势,而不是秒数或精确指令数。

因此,一个常数很大的 O(n) 算法在小数据上可能暂时比某个 O(n²) 算法慢。但随着 n 持续增加,增长更快的复杂度通常会逐渐成为主要问题。分析复杂度的价值,正是在运行程序之前预判这种扩展风险。

判断复杂度先找重复规模

阅读算法时,可以先观察最主要的重复工作。固定次数的操作通常是 O(1);一次遍历 n 个元素通常是 O(n);两个都遍历 n 次的嵌套循环经常形成 O(n²);若每轮都把问题规模减半,则常见 O(log n)。

大 O 的作用不是替代性能测试,而是在还没有具体机器和真实数据时先判断算法的增长趋势。数据规模较小时,多种方案可能差异不明显;当规模扩大后,增长阶数往往比某次测试中几毫秒的差距更值得关注。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用大 O 表示算法增长速度

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通