排序算法压缩

Question

设 A 和 B 是解决同一问题的两个算法。 声明：如果 A 比 B 快，无论是在最坏情况还是在平均情况下，那么， 必然地，A 比 B 快，在最好的情况下也是如此。

Answer 1

没有。考虑合并排序与插入排序。归并排序在最佳、平均和最差情况下总是 O(n log n)。插入排序在平均和麦汁情况下是 O(n^2)；然而，最好的情况是 O(n)。