Big O 记号：A-level 计算机科学真正的要求

Big O 记号出现在每份主要的 A-level 计算机科学规范中（AQA、OCR、Edexcel），它让很多学生困惑不是因为数学难，而是他们从未看到它与真实代码的结合。这是一份实践指南，说明你需要知道什么以及如何回答关于它的考试问题，而不是罗列一堆废话。

Big O 实际衡量什么

Big O 描述的是算法的运行时间（或内存使用）如何随着输入大小（通常称为 n）而增长。它不是秒数的秒表测量。这是描述增长速率的方式，这样你可以比较不同硬件上的算法。

当你写 O(n) 时，你是说：如果我将输入翻倍，工作量大约翻倍。O(n²) 意味着输入翻倍时，工作量大约是四倍。这种关系就是考官希望你识别的，而不是精确的操作计数。

你必须掌握的复杂度

对于 A-level，这些是一次又一次出现的：

• O(1) – 常数时间。按索引访问数组元素：arr[5]。数组有多大都无关紧要。
• O(log n) – 对数。对排序列表的二分查找。每一步都将剩余搜索空间减半。
• O(n) – 线性。对列表的单一循环，像线性搜索那样逐个检查每项。
• O(n log n) – 线性对数。归并排序和快速排序（平均情况）落在这里。
• O(n²) – 二次。在相同数据上嵌套循环，这正是冒泡排序、插入排序和选择排序所做的。
• O(2ⁿ) – 指数。没有记忆化的朴素递归斐波那契。增长快速。

你应该能够看着伪代码立即说出是其中哪一个，因为那基本上是被测试的内容。

阅读代码的复杂度

每次都有效的方法：计算循环并看它们如何与 n 相关。

# O(n) - 一个循环，一遍通过
for i in range(n):
    print(i)

# O(n^2) - 嵌套循环，都与 n 相关
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - 搜索空间每次迭代都减半
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

嵌套循环中，如果内循环的范围取决于 n，即使看起来略有不同（像 for j in range(i) 而不是 for j in range(n) —— 那在整体上仍然是二次的，只是常数因子有所不同），它仍然是 O(n²)。

注意根本不取决于 n 的循环。总是运行 10 次的循环，无论输入大小如何，都是 O(1)，即使存在循环。考官喜欢在这方面设置陷阱。

常见排序算法及其 Big O

这是一个最喜欢的考试题目，因为它同时结合了两个规范：排序算法和复杂度。

算法	最佳情况	最坏情况
冒泡排序	O(n)	O(n²)
插入排序	O(n)	O(n²)
归并排序	O(n log n)	O(n log n)
二分查找	O(1)	O(log n)
线性搜索	O(1)	O(n)

归并排序的一致性（最佳和最坏情况相同的复杂度）如果问题问为什么你会在大数据集上选择它而不是冒泡排序，值得明确提及。冒泡排序的最佳情况 O(n) 仅当有提前退出优化时才适用，即当一遍没有发生交换时—— 如果你提到它，提出这个细节，因为一些考试委员会期望它。

学生失分的地方

最大的问题：写