Sno*_*man 3 algorithm big-o mergesort discrete-mathematics
Snape的"不友好的向导算法"教科书声称合并排序的运行时间为O(n ^ 4).这个说法是否正确？
解决方案:是的.这种说法在技术上是正确的,因为O(n ^ 4)仅给出算法花费多长时间的上限.然而,这是一个令人讨厌的无益答案,因为紧张局限是?(n log n).
我不太明白解决方案的内容.O(n ^ 4)如何正确？
对于算法运行时,Big O表示法是最坏情况下的上限.
由于O(n ^ 4)高于mergesort的最坏情况时间,因此它在技术上是正确的,因为它确实提供了一个约束 - 即.Mergesort的性能永远不会比O(n ^ 4)差.
然而,这是无益的,因为运行时间一个更好的表达是O(n log n)的,这是"严格的"开往合并排序