归并排序运行时间 BigO
斯内普的《巫师不友好算法》教科书声称合并的运行时间 排序是 O(n^4)。这种说法正确吗？
解决方案：是的。这个说法在技术上是正确的，因为 O(n^4) 只给出了一个上限 限制算法需要多长时间。然而，这是一个令人讨厌的无用答案， 因为紧界是 θ(n log n)。
我不太明白解决方案的内容。 O(n^4) 怎么可能是正确的？
Snape’s “Unfriendly Algorithms for Wizards” textbook claims the running time of merge
sort is O(n^4). Is this claim correct?
Solution: Yes. This claim is technically correct, because O(n^4) only gives an upper
bound for how long the algorithm takes. However, it’s an obnoxiously unhelpful answer,
since the tight bound is Θ(n log n).
I'm not quite understanding what the solution is stating. How can O(n^4) be correct?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
大 O 表示法是算法运行时最坏情况的上限。
由于 O(n^4) 高于合并排序的最坏情况时间，因此它在技术上是正确的，因为它确实提供了一个界限 - 即。归并排序的性能永远不会低于 O(n^4)。
然而，这是没有帮助的，因为运行时间的更好表达是 O(n log n)，这是合并排序的“最紧”界限
Big O notation is an upperbound on the worst case for an algorithm runtime.
Since O(n^4) is above the worst case time of mergesort it is technically correct because it does provide a bound - ie. Mergesort will never have a performance worse than O(n^4).
However, it's unhelpful because a better expression of the running time is O(n log n), which is the "tightest" bound for merge sort
Big-O 是一个集合，其中包括所有运行速度与 (foo) 或更快的东西。 Little-O 是一组运行速度比 (foo) 快的东西。虽然说归并排序是 O(n^4) 是正确的，但它不是很有用，因为它是 Theta(n log n)。说归并排序是 o(n^4) 稍微有用一些，因为 Little-o 表示法从未用于暗示 big-theta 运行时。
更复杂的是，当大θ更合适时，通常会使用大O，因为大多数键盘没有θ。
Big-O is a set, which includes everything that runs as fast as (foo) or faster. Little-O is a set of things that run strictly faster than (foo). While it's correct to say mergesort is O(n^4), it's not very useful, because it's Theta(n log n). Saying that mergesort is o(n^4) is marginally more useful, because little-o notation is never used to imply big-theta runtime.
Further complicating matters, big-O is often used when big-theta would be more appropriate, just because most keyboards don't have a theta.