大O(n logn)不优于O(n ^ 2)

Question

任何算法示例我们何时比O(n logn)更喜欢Big O(n ^ 2)时间复杂度？我在某处看到过这个问题,但没有找到答案.

Answer 1

对于一个大问题,O(n log n)总是会超过O(n ^ 2).对于一个小问题,big-O表示法隐藏的常数因子可能会使您更喜欢O(n ^ 2)算法.例如,O(n log n)快速排序比O(n ^ 2)插入排序快,但是当分区变小(少于十个元素)时,一些快速排序实现切换到插入排序.

Answer 2

选择具有更高时间复杂度的算法有几个原因:

• 速度:渐近复杂度仅适用于大于某些n_0的n值.此外,它假定下面的某个机器仅部分匹配具有多级缓存和受限内存的真实机器.
• 空间:某些算法需要比其他算法更多的空间,因此无法实现.而且,这可能只会影响真机的速度.例如,引用的位置对缓存命中或未命中有影响,这就是为什么Quicksort比Mergesort表现更好的原因.
• 实施复杂性:在某些情况下,性能损失可以忽略不计,但开发时间却没有.