关于时间复杂度和大O表示法的问题

Question

算法 A 和 B 的最坏情况运行时间分别为 O(n) 和 O(logn)。因此，算法 B 总是比算法 A 运行得更快。对还是错？

我认为答案是错误的，因为 O(logn) 总是比 O(n) 好

Answer 1

我认为答案是错误的，因为 O(logn) 总是比 O(n) 好

这是一个矛盾。如果您相信 O(log𝑛) 总是比 O(𝑛) 好，那么 B 将是“总是更好”的那个。

但更重要的是，该陈述仍然是错误的，但不是出于您给出的（混合的）原因：如果您只知道算法的时间复杂度，则对于某些给定的输入，您无法预测算法与另一个算法相比的运行速度。

例如，假设我们有一个恰好为 1 毫秒的执行单元，并且我们知道算法 A 需要在其循环之外执行其中 10 个单元，然后需要在循环的每次迭代中执行 1 个单元。我们还假设迭代次数等于 𝑛。那么 A(𝑛) 的总执行时间将需要 10+𝑛 毫秒。

假设 B 有一个执行 log₂𝑛 次的循环，并且每次迭代需要执行 100 个单元。该循环之外还有 1000 个单位的开销。那么 B(𝑛) 总共执行需要 1000+100log₂𝑛 毫秒。

现在令 𝑛 为 128。

• A(𝑛)的总执行时间为138毫秒。

• B(𝑛)的总执行时间为1700毫秒。

这次A获胜。

现在令 𝑛 为 65536。

• A(𝑛)的总执行时间为65546毫秒。

• B(𝑛)的总执行时间为2600毫秒。

现在 B 获胜。

结论：如果只知道时间复杂度，你无法确定哪一个运行得更快。时间复杂度仅说明渐近行为。在这种情况下，这意味着如果您采取足够的𝑛大（待确定多大大），算法B将比A更快完成。