algorithm - 最坏情况时间复杂度为 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 更快(即扩展性更好)，即使它具有更大的最坏情况复杂性。