假设您的算法n^2 + 1000 n在n元素上运行时实际执行计算.现在n = 1你需要1001次计算,而n = 2你需要2004年.线性增长的差异很小,你很难发现二次贡献!
然而,渐近地,您的算法采用O(n ^ 2)步,因此渐近(因为n变大)将输入大小加倍,使运行时增加四倍.但是对于我们的小值,从1加倍到2并没有使运行时间翻两番!低阶项是n,并且其系数(1000)与前导项的系数n^2(为1)相比较大.
这表明渐近复杂性如何不说特定的,特别是小值.这仅仅是关于行为n变大的限制性陈述.
使用 O 表示法时，您可以指定函数的最大项，即性能限制。例如，如果性能始终受f = c 3 n 3 + c 2 n 2 + c 1 n + c 0约束，则您可以说它是 O(n 3 )。作者是说，当 n 很小时，系数对性能的影响可能比 n 更大，例如，如果 c 2非常大而 c 3非常小，则性能可能看起来是 O(n 2 )，直到如果仅考虑 n 的特定小实例的相对性能，则 n 的大小将主导系数。