两个O(n^2)算法的时间复杂度相同吗？

Question

我对这个问题并不完全理解：

对于一个给定的n值，两个O（n^2）算法将始终需要相同的时间。 正确还是错误？ 请解释。

我认为答案是错误的，因为在我的理解中，渐进时间复杂度只衡量两个算法以O（n^2）时间运行，然而其中一个算法可能需要更长的时间，例如它可能有额外的O（n）组件。 就像O（n^2）与（O（n^2）+O（n））之间的差异。

我不确定我的逻辑是否正确。 感谢您的帮助。

- RVER12321312

---

除了低阶项，大O()忽略常数因子。运行时间为1000n和.001n的算法都是O(n)，但对于给定的n，第一个比第二个慢一百万倍。有很多算法在渐近意义下比通常用来解决同一问题的算法更快。这种情况的原因几乎总是渐近“快”算法的运行时间中存在大的常数因子。 - Gene

这个问题更适合在计算机科学Stack Exchange上提问，尽管从历史上看，在这里提问也是非常合适的。 - Nayuki

Answer 1

是的，你说得对。大O符号表示时间复杂度的上限。有时可能会添加一些额外的常数项c或者小于n的项，这些项不会被考虑在内。

此外，

for i = 0 to n
    for j = 0 to n
        // some constant time operation
    end
end   

而

for i = 0 to n
    for j = i to n
        // some constant time operation
    end
end   

这两个算法的渐近时间复杂度都是 O(n^2)，但它们所需的时间不同。

大O分析的概念不是为了计算程序执行的精确时间，也不是计算循环迭代的次数。相反，它指示算法随着 n 的增长速率。

- Kaidul

Answer 2

答案是正确的，但解释不够充分。首先，大 O 表示法允许任意常数因子，因此 n² 和 100*n² 都在 O(n²) 中，但显然后者始终更大。另一个原因是该表示法仅给出上界，因此运行时间为 n 的算法也在 O(n²) 中，因此其中一个算法实际上可能是线性的。

- Henry