两段代码在一个小测试用例上可能产生完全相同的结果,却在真实数据到来后表现出截然不同的行为。大O记法是计算机科学家精确描述这种差异的方式——通过数学方式描述随着输入规模增加,操作数量如何增长。
A-Level拓展
“O”真正的意思
大O描述的是一个算法的增长率——随着输入规模(传统上称为n)增加,操作数量如何增长。它刻意忽略常数因子和小项,因为它要回答的问题是“这如何增长”,而这个问题的答案不取决于你用的是哪台计算机。
真正重要的增长率
一小部分增长率涵盖了几乎所有你会遇到的算法,按数据增加时从最好到最差排列:
- O(1) — 常数。无论输入规模多大,步骤数都相同,比如检查一个列表是否为空。
- O(log n) — 对数。随着n增加,操作数增长得非常缓慢——比如在已排序列表中的二分搜索。
- O(n) — 线性。输入翻倍,工作量也翻倍——比如遍历一个未排序列表中的每一个元素一次。
- O(n²) — 平方。输入翻倍,工作量变成四倍——典型的例子是把每个元素与其他每个元素比较。
对于较小的n,这些曲线看起来很相似——真正决定哪个算法能在真实世界数据中存活的差异,只有当n变大时才会出现,而这恰恰是大O记法专门设计来描述的那个范围。
Try it yourself — drag the slider to change the input size (n), and watch how many operations each growth rate actually needs.
Input size: n = 10
At n = 10, an O(n²) approach needs 100 operations — 10× more than the O(n) approach doing the exact same job.
一个O(n²)的平方算法,对10个元素执行100次操作,对1000个元素会执行1,000,000次操作——不是100倍数据带来100倍工作量,而是10,000倍的工作量。
考试式问题
一个算法处理4个项目需要8次操作,处理8个项目需要32次操作,处理16个项目需要128次操作。确定它的大O增长率,并展示你的推理过程。 [3分]
显示范例答案与得分点
- 比较n翻倍的连续情况:4 → 8,以及8 → 16 (1分)
- 操作次数每次都翻两番(变为4倍):8 → 32(×4),以及32 → 128(×4) (1分)
- 当n翻倍导致操作次数变为4倍(×4 = ×2²)时,这就是二次增长的特征:O(n²) (1分)
考官关注的重点: 找出n翻倍与操作次数所产生的倍数之间的具体规律——这个比值(此处为每次翻倍×4)才是真正用来确定增长率的依据,而不是单纯看原始数字。
常见错误: 仅仅因为数字「持续变大」就假设是线性增长,而没有检验能区分O(n)(n每翻倍×2)和O(n²)(每翻倍×4)的翻倍关系。
为什么增长率的差异在实践中很重要
用小测试数据,一个O(n²)算法和一个O(n log n)算法可能都在一瞬间完成——差异看不出来。把同样的输入增长到一个真实产品实际处理的规模,O(n²)的方法可能需要真正的几个小时,而O(n log n)的方法只需要几秒钟。
为什么这超越写出正确的代码而真正重要
任何程序员都能写出产生正确答案的代码。如果计算机科学是您或您的孩子需要通过解释一种方法为什么比另一种更好来理解的内容,而不仅仅是语法,这正是我们GCSE与A-Level计算机科学个别指导所提供的,您可以在这里查看完整的学习路径。
常见问题
为什么我们忽略常数和小项——这不会丢失有用的信息吗?
大O记法是刻意设计来回答一个特定问题的——当输入变得非常大时,运行时间如何增长——而n越大,常数就越不重要。大O记法并不能说明性能的全部情况,但它能正确预测,一旦数据足够大,哪个算法会胜出。
更低的大O总是实践中更好的选择吗?
不一定——对于小输入,一个大O较差但常数因子小得多的算法,实际上可能运行得更快,因为“更好”的算法开始占优的那个交叉点,可能只在n非常大的时候才会出现。
大O在日常生活中实际上是如何被程序员使用的,而不仅仅是在面试中?
这是开发者用来预测一种方法在真实(非常大)的数据到来时是否还能奏效的方式。在未排序的列表中搜索是O(n);在已排序的列表中二分搜索是O(log n)——10个元素时这种差异看不出来,1000万个元素时却是巨大的。
读者评分与评价
从多个维度为这篇文章打分——您的评价既能帮助其他读者,也能帮助我们不断改进。
这篇文章对您有帮助吗?
告诉我们您的想法——可以是需要更正的地方、尚未解答的问题,或您希望我们接下来讲解的主题。
想直接沟通吗？ 在方便的时间预约免费视频通话：简短问题15分钟，其他问题30分钟。时间以您所在的时区显示。
关于作者
Sudershan Soni
Mostak Services 的创始人兼首席导师——拥有硕士学位的数学、科学、计算机科学与 STEM 导师,拥有超过20年的职业经验,通过在线授课为全球从 11+ 和 GCSE 到 A-Level 及更高阶段的学生提供教学。
阅读完整履历