非渐近场景下O(cn)算法的运行速度是否至少和O(n)算法一样快？

答案是否定的：即使c1>c2，也完全不能确定O(c1·n)算法的运行速度不低于O(c2·n)的算法。

大O时间复杂度的设计初衷是描述数据规模趋近于无穷大时，算法执行效率的增长趋势，本身在定义阶段就会忽略常数系数、低阶项的影响，所以同阶复杂度（此处均为线性阶O(n)）的算法，单纯对比抽象后的复杂度系数，完全无法推导实际运行性能。

你提到的两个场景就是非常典型的反例：

• 数组最值查找场景：两次遍历分别查最大值、最小值的方案复杂度为O(2n)，单次遍历同步统计两个值的方案复杂度为O(n)。但忽略编译器优化的前提下，单次遍历每次迭代需要执行的指令数是两次遍历单次迭代的2倍，二者实际运行时间可能完全一致。
• 数组反转场景：新建数组遍历填充的方案复杂度为O(n)，从两端向中间遍历、用异或交换算法交换对称位置元素的方案复杂度为O(1/2 n)。但后者每次迭代需要执行至少3次异或操作，就算改用临时变量交换也需要额外2条赋值指令，实际运行效率反而可能比O(n)的方案更差。

在实际代码编写中，如果两个算法属于同阶复杂度，不要单纯根据简化的复杂度系数做选型，需要结合实际压测性能、代码可读性、可维护性综合判断：如果常数系数更高的方案可读性明显更优，且实测性能和低系数方案没有可感知的差距，完全可以优先选择前者。

内容的提问来源于stack exchange，提问作者Miguel Pinheiro