我们什么时候要考虑运行时的常量？

Question

假设我有两个算法：A()和B()，算法A()精确地取O(3n^2)，而算法B()取O(n^2)。虽然这两种算法都是在二次时间内运行的，但我们可以说算法B的运行速度比二次时间快吗？

我知道，在分析算法的运行时间时，我们忽略了常量，但是当我们在分析算法时需要考虑常量时，我想问一下情况。

谢谢

Answer 1

您可能想看看this SO answer。

从这一答复中：

总之，由于大O只谈论增长率的相对类别，它忽略了常数因素。然而，这些常数是绝对重要的；它们只是与渐近分析无关。

因此，它在Big表示法方面可能没有什么不同，但在现实生活中，您的算法B确实会运行得更快。

Answer 2

你的两种算法的渐近复杂度是一样的，但其中一种肯定比另一种更快。

在这种情况下，A有一个更大的常数，因此它可能更慢，但可能还有其他因素(例如算法实现中的实现细节和它正在运行的硬件中的实现细节)可能会影响平衡。