大O增长：每一类复杂度真正的代价

您的数据

两个算法正面对比

常数就是这套记号扔掉的一切：内存分配、缓存未命中、每一步内部的活儿。给其中一个算法一个更重的常数，看看它从哪里开始不再重要。

这个页面不读你的循环。从源码去猜复杂度，是披着测量外衣的猜测：循环可能提前跳出，里面一次调用就可能藏着真正的开销，而递归很少能照字面读出它在做什么。类别由你来选；从那之后页面算的都是精确的。

结果

按本页初始的数字，交叉点在 439 个元素。有人在两百条的列表上换用“更好的类别”，结果只是让程序更慢、代码更难，而记号并没有提醒——因为记号讲的是最终会怎样，不是你这里会怎样。

在这个规模下的每一类

最后一列才值得盯着看，因为那是没人会随身记住的一列。线性工作翻一倍。平方工作变四倍。指数工作是被平方：已经有一千个元素时，把输入翻倍会让代价乘以二的一千次方，一个三百零二位的数。

阶乘的糟糕，跟“翻倍”完全是另一回事。多加一个元素，代价就乘以新的个数：第二十一个元素，要花掉整个二十元素问题的二十一倍。所以精确求解二十座城市的旅行商问题是 2.4 百万百万百万步，按每秒十亿次算是七十七年；而同样二十座城市在二的 n 次方下，千分之一秒就结束了。

这也解释了为什么类别之间的差距在小规模上乏味、在大规模上残酷。十个元素时，n log n 和 n 平方相差三倍，没有哪个用户会察觉。一千个元素时相差一百倍，一百万个时相差五万倍。同样两个算法，同样的代码，变的只有输入。

所以，诚实地读一个复杂度类别，它是关于曲线形状的承诺，不是关于速度的承诺。它说的是输入变大时代价如何反应，完全没说在你今天这台机器上、在你真正的规模下它快不快。