两个算法都是O(n log n)，为何实测仍能差十倍：复杂度、常数与基准条件怎样分开

学生写了两个排序程序，分析报告都标为O(n log n)。他拿一万个随机整数各跑一次，A用了十二毫秒，B用了一百二十毫秒，于是结论写成“A的算法复杂度比B好十倍”。数字是真的，结论却把三个问题混在一起：增长阶、当前实现和这一次测量。

Big-O不是秒表。它描述输入规模增大时，资源需求不会超过某个增长上界。实测时间则来自具体代码、具体数据、具体运行时和具体机器。两个层面需要互相解释，但任何一个都不能替代另一个。

先弄清O(n log n)到底说了什么

NIST将Big-O定义为算法随问题规模n变化的理论时间或内存上界。形式上，它表示当n大到超过某个门槛后，函数不会超过目标函数的某个固定倍数。这里的固定倍数和门槛存在，却没有被符号写出来。

因此，O(n log n)没有承诺一万个元素需要多少毫秒，也没有说两个同阶函数彼此只差一点。一个实现可能近似二乘n log n，另一个可能近似五十乘n log n加上一大段初始化成本；两者仍属于相同增长阶。

MIT的渐近分析讲义把这种观察称为从高处看函数增长。常数倍和较低阶项会在规模足够大时被主导项吸收，但它们在课程实验、网页请求或手机程序常见的有限规模里可能仍然占主导。

更常见的误解是把O写成等号。MIT和NIST都区分上界与紧确界：O只约束上界，Omega约束下界，Theta才同时约束上下界。一个线性函数也可以宽松地写成O(n²)，所以看到两个实现都标O(n log n)时，还要问这个界是否紧确，讨论的是最坏、平均还是摊还情形。

相同增长阶为什么会出现十倍差距

第一类差距来自常数。一个排序实现每轮只交换索引，另一个复制完整对象；抽象上都做n log n层工作，单次操作代价却不同。函数调用、边界检查、分配对象和比较器调用都可能成为常数的一部分。

第二类来自低阶项与固定成本。建立辅助数组、编译正则、启动线程或加载模块可能与n无关，也可能只按n增长。当输入很小时，这些成本比主导项更大；输入扩大后，曲线才可能出现交叉。

第三类来自内存行为。连续数组的顺序访问通常比指针分散的对象更容易利用缓存。理论模型若把每次内存访问都视为同一成本，就不会显示缓存未命中、内存带宽和分支预测的差别。

这三类原因不会推翻渐近分析。相反，它们说明理论结论必须写清抽象了什么。若A在当前规模快十倍，但曲线斜率增长更快，扩大输入后仍可能被B超过；只有测多个规模，才能看到交叉点是否存在。

计算模型决定你在数什么

NIST指出，任何执行量都隐含或明确依赖某种计算模型。某个问题的限制可能是浮点乘法，另一个可能是网络消息；还可以统计比较、元素移动、磁盘访问、内存使用或墙钟时间。

若报告只写“更快”，读者不知道比较的是CPU时间、实际等待时间、内存峰值还是磁盘吞吐。一个批处理算法可能使用更多内存换取较短墙钟时间；另一个节省内存，却增加随机磁盘访问。谁更好取决于任务限制。

课程实验常采用随机存取机器的简化视角，把基本操作视为固定成本。这适合证明增长阶，却不表示真实处理器上的所有操作同价。字符串比较取决于共同前缀长度，大整数运算取决于位数，跨进程消息还包含序列化和调度。

在实验说明中写下资源指标：比较次数、移动次数、峰值内存、CPU时间或墙钟时间。理论部分说明为什么选择它，实测部分说明怎样取得它。两个算法只有在同一问题、同一指标下才适合直接对照。

输入不仅有大小，还有形状

只写n等于一万仍不够。排序输入可以随机、已经有序、逆序、包含大量重复值，或由少量大对象组成。算法的分支、递归深度、比较次数与内存访问会随分布改变。

如果一个实现针对近乎有序数据做了优化，它在随机输入上未必显出优势。若比较函数读取长字符串，元素数量相同也不代表比较成本相同。把两组不同数据交给两个算法，得到的差异无法归因于实现。

建立一份由固定种子产生的输入集合，让两个实现读取完全相同的数据。至少覆盖小、中、大三个规模，并选两到四种与实际任务相关的分布。每个测试都保留生成规则和输入摘要，避免只留下一个无法重建的压缩包。

正确性检查必须先于计时。两个程序输出不一致时，速度比较没有意义。可以核对输出是否有序、元素多重集合是否保持一致，并对小样本与可信实现交叉验证。不要把省略工作或错误结果产生的“加速”写成优化。

微基准要把准备工作说清楚

Python官方timeit用于测量小段代码，并专门避免常见计时陷阱。它把setup阶段排除在被测时间之外。这很适合隔离核心操作，却也意味着数据生成、导入模块或建立连接的成本可能没有进入结果。

假设A需要昂贵的预处理后查询很快，B无需预处理但每次查询稍慢。只测查询会偏向A；若真实任务只查询一次，端到端结果可能相反。报告应同时给出准备成本、单次操作成本和预期调用次数。

timeit默认暂时关闭垃圾回收，让独立测量更容易比较。若被测代码会大量分配对象，而真实应用必须承担回收成本，关闭回收就改变了问题。Python文档明确说明，此时应在setup中重新启用垃圾回收。

计时工具本身也有开销。函数包装、循环和计时器调用在极短片段中可能占据显著比例。timeit允许自动增加循环次数，使总时长达到可测范围；报告微秒级差异前，应测空操作基线，并确认差距明显大于计时开销。

重复测量不是把五次随便平均

操作系统会调度其他进程，处理器频率会变化，缓存可能冷或热。Python文档建议重复计时，并查看完整结果向量。在典型微基准里，最低值可作为当前机器运行该片段速度的下界线索，较高值常来自其他进程干扰。

这不表示任何实验都应该只发布最低值。最低值适合回答“在这台机器、受干扰较少时能多快”，端到端服务则必须承担调度、回收和输入输出。更透明的做法是保留全部重复结果，同时报告最低值、中位数和测试目的。

预热也要固定。解释器缓存、即时编译、文件系统缓存或CPU升频都会让前几次运行不同。可以预先运行固定次数但不计入结果，并在报告里写明；也可以刻意测冷启动，但不能把冷启动A与预热后的B比较。

每轮测试的顺序也可能偏向后运行者。交替执行A与B，或使用固定且可复查的随机顺序，可以减少温度和后台负载随时间变化造成的偏差。若差距与顺序一起翻转，应先调查实验条件。

一个可复查的基准应该留下什么

第一部分是理论声明。写出问题定义、输入规模n代表什么、讨论的情形和预期增长阶。若只有Big-O上界，不要把它改写成紧确Theta；若平均情形依赖随机分布，也要把分布假设写出来。

第二部分是实现身份。保存代码提交编号、语言和运行时版本、编译参数、依赖版本，以及是否启用优化。相同源代码在不同解释器或编译器下可能采用不同内部路径，版本不能只写“最新版”。

第三部分是机器与状态。记录处理器、内存、操作系统、电源模式、虚拟化环境和同时运行的重要程序。无需假装完全消除噪声，但要让别人知道结果在哪种环境成立。

第四部分是输入。保存构造规则、随机种子、规模与分布；无法公开原始数据时，给出脱敏统计。

第五部分是测量协议。说明准备阶段是否计时、是否启用垃圾回收、预热次数、循环次数、重复次数、计时器和指标。Python timeit默认采用高分辨率性能计时器，但跨语言比较仍要确认双方测量的是同一种时间。

第六部分是原始结果。不要只贴一张柱状图或一个“快十倍”。保留每次读数、异常值、失败运行和排除理由。以输入规模为横轴画曲线，比单点倍率更容易看出增长趋势和交叉位置。

用一个排序实验走完整流程

假设比较归并排序A与混合排序B。理论上，两者在选定情形都给出Theta(n log n)。实验准备四种输入：随机、有序、逆序和高重复值；规模从一千增加到一百万，每组由固定种子生成。

两个实现对同一份不可变输入的副本运行，计时前验证输出。数据生成与复制分别计时，不混入核心排序；另做端到端测试，把读取、复制、排序和写出全部纳入。

每个组合预热若干次，再交替重复多轮。保存完整向量，并报告最低值描述受干扰较少的核心速度，中位数描述典型观测。若B在小规模快十倍、到大规模只快两倍，这说明常数优势仍在，但不能据此说复杂度好了十倍。

再检查峰值内存和移动次数。A可能稳定但使用额外数组，B可能原地操作却有更复杂分支。对内存受限设备，后者也许更合适；对吞吐优先的服务器，前者可能更稳。结论应回到任务限制。

哪些结论可以写，哪些不能写

可以写：“在Python 3.14.6、指定处理器与四种输入分布下，B在一万到一百万元素范围的核心计时中位数较低。”这句话保留了实现、环境、规模、数据和指标。

不能写：“B的算法复杂度快十倍。”复杂度不是速度单位，倍率也不是增长阶。也不能从随机整数推广到长字符串、磁盘数据或其他语言，因为比较成本和资源瓶颈已经改变。

如果理论增长阶不同，实测仍应寻找交叉点，而不是期待小输入立即体现优势。一个O(n²)的简单实现可能在很小n上胜过高固定成本的O(n log n)实现；这不否定大规模趋势。

微基准也不能替代真实工作负载。它能定位某个函数的成本，却未包含解析、网络、磁盘、锁竞争和错误处理。最终选型应增加一层端到端测试，并使用接近实际的调用比例与数据。

结论把理论和测量接起来

渐近记号省略常数和低阶项，实际实现又把抽象步骤映射到缓存、分配、解释器与系统调用，因此同阶算法在有限规模上可以相差很大。理论分析比较规模增长，微基准隔离小片段成本，端到端测试保留准备、输入输出和运行时成本；三者回答不同问题。

固定代码、运行时、硬件和数据构造规则，分层重复测量并保存结果、异常值与版本，让别人能够重做。

Big-O不是实际秒数，同阶算法不会自动在所有输入上接近。单机最快一次只能提供当前受控环境的局部下界线索，不能证明算法在其他输入、机器、语言或真实工作负载中普遍更优。

资料来源

• MIT OpenCourseWare：《6.006 Recitation 1 Notes: Asymptotic Complexity, Peak Finding》，发布或更新于 2011-09-09
• NIST：《big-O notation》，发布或更新于 2024-10-30
• NIST：《complexity; model of computation》，发布或更新于 2024-10-30
• Python Software Foundation：《timeit — Measure execution time of small code snippets》，发布或更新于 2026-07-27