algorithm - 合并排序运行时间 BigO

Question

Snape 的“Unfriendly Algorithms for Wizards”教科书声称归并排序的运行时间为 O(n^4)。这种说法正确吗？

解决方案：是的。这种说法在技术上是正确的，因为 O(n^4) 只给出了算法需要多长时间的上限。然而，这是一个令人讨厌的无用答案，因为严格的界限是Θ(n log n).

我不太明白解决方案在说明什么。O(n^4) 怎么可能是正确的？

Answer 1

大 O 表示法是算法运行时最坏情况的上限。

由于 O(n^4) 高于合并排序的最坏情况时间，因此它在技术上是正确的，因为它确实提供了一个界限 - 即。合并排序的性能永远不会比 O(n^4) 差。

然而，它没有帮助，因为运行时间的更好表达是 O(n log n)，这是合并排序的“最严格”界限

Answer 2

Big-O 是一个集合，其中包括运行速度与 (foo) 或更快的所有内容。Little-O 是一组运行速度严格快于 (foo) 的东西。虽然说归并排序是 O(n^4) 是正确的，但它并不是很有用，因为它是 Theta(n log n)。说归并排序是 o(n^4) 稍微有用一些，因为 little-o 符号永远不会用于暗示 big-theta 运行时。

更复杂的是，当 big-theta 更合适时，通常使用 big-O，因为大多数键盘没有 theta。