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

Question

我无法完全理解这个问题：

对于给定的 n 值，两个 O(n²) 算法将始终花费相同的时间量。对或错？解释一下。

我认为答案是错误的，因为根据我的理解，我认为渐近时间复杂度仅衡量两个算法运行在 O(n²)时间，但是一种算法可能需要更长的时间，因为它可能有额外的 O(n) 组件到算法中。就像 O(n²) vs (O(n²) + O(n)).

我不确定我的逻辑是否正确。任何帮助将不胜感激。

Answer 1

是的，你是对的。 Big Oh 表示法描述了时间复杂度的上限。可能会添加一些额外的常数项 c 或更小的 n 项，例如 O(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) 渐进的，但不会花费相同的时间。

big Oh分析的概念不是计算一个程序执行的精确时间，不是计算一个循环迭代了多少次。相反，它表示算法的 增长率 和 n。

Answer 2

答案正确，但缺少解释。

一方面，大 O 表示法允许任意常数因子。所以 n² 和 100*n² 都在 O(n²) 但显然是第二个总是更大。

另一个原因是该符号仅给出上限，因此即使 n 的运行时间也在 O(n²) 中，因此其中一种算法实际上可能是线性的。

Time complexity will two O(n^2) algorithms take the same amount of time?