O（n）最坏情况时间复杂度的算法是否总是比O（n ^ 2）最坏情况时间复杂度的算法快？

Question

这个问题出现在我的算法课上。这是我的想法：

我认为答案是否定的，具有O（n）的最坏情况时间复杂度的算法并不总是比O（n ^ 2）的最坏情况时间复杂度的算法快。

例如，假设我们有总时间函数S（n）= 99999999n和T（n）= n ^ 2。那么显然S（n）= O（n）和T（n）= O（n ^ 2），但是对于所有n <99999999，T（n）比S（n）更快。

这个推理有效吗？我有点怀疑，尽管这是一个反例，但它可能是错误观念的反例。

非常感谢！

Answer 1

对于任何给定的输入，Big-O表示法都没有说明算法的速度。它描述了时间如何随着元素数量的增加而增加。如果您的算法以固定的时间执行，但是时间是1000亿年，那么对于大范围的输入，它肯定比许多线性，二次甚至指数算法要慢。

但这可能并不是问题所在。问题是，具有最坏情况复杂度O（N）的算法A1是否总是比具有最坏情况复杂度O（N ^ 2）的算法A2 快？通过更快，它可能指的是复杂性本身。在这种情况下，您只需要一个反例，例如：

• A1具有正常的复杂度O（log n），但最坏情况的复杂度O（n ^ 2）。
• A2具有正常复杂度O（n）和最坏情况复杂度O（n）。

在此示例中，即使A1具有更大的最坏情况复杂度，它通常也比A2更快（即缩放更好）。