Snape 的“Unfriendly Algorithms for Wizards”教科书声称归并排序的运行时间为 O(n^4)。这种说法正确吗?
解决方案:是的。这种说法在技术上是正确的,因为 O(n^4) 只给出了算法需要多长时间的上限。然而,这是一个令人讨厌的无用答案,因为严格的界限是Θ(n log n).
我不太明白解决方案在说明什么。O(n^4) 怎么可能是正确的?
Snape 的“Unfriendly Algorithms for Wizards”教科书声称归并排序的运行时间为 O(n^4)。这种说法正确吗?
解决方案:是的。这种说法在技术上是正确的,因为 O(n^4) 只给出了算法需要多长时间的上限。然而,这是一个令人讨厌的无用答案,因为严格的界限是Θ(n log n).
我不太明白解决方案在说明什么。O(n^4) 怎么可能是正确的?
大 O 表示法是算法运行时最坏情况的上限。
由于 O(n^4) 高于合并排序的最坏情况时间,因此它在技术上是正确的,因为它确实提供了一个界限 - 即。合并排序的性能永远不会比 O(n^4) 差。
然而,它没有帮助,因为运行时间的更好表达是 O(n log n),这是合并排序的“最严格”界限
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。