任何算法示例何时我们更喜欢大 O(n^2) 时间复杂度而不是 O(n logn)？我在某处看到过这个问题，但没有找到答案。
问问题
897 次
4 回答
8
对于一个大问题，O(n log n) 总是会击败 O(n^2)。对于一个小问题，大 O 符号隐藏的常数因子可能会导致您更喜欢 O(n^2) 算法。例如，O(n log n) 快速排序比 O(n^2) 插入排序快，但是当分区变小（少于 10 个元素）时，一些快速排序实现会切换到插入排序。
于 2016-02-05T15:55:48.133 回答
7
选择具有更高时间复杂度的算法有几个原因：
- 速度：渐近复杂度仅适用于大于某个 n_0 的 n 值。此外，它假设某台机器下面仅部分匹配具有多级缓存和受限内存的真实机器。
- 空间：一些算法比其他算法需要更多的空间，因此无法实现。此外，这可能只会影响真机上的速度。例如，引用的位置对缓存命中或未命中有影响，这就是 Quicksort 比 Mergesort 执行得更好的原因。
- 实现复杂性：在某些情况下，性能损失可以忽略不计，但开发时间却不是。
于 2016-02-05T16:04:57.583 回答
1
许多天真的 O(n^2) 算法在小输入上比它们更复杂的 O(n log(n)) 兄弟更快。
例如，GNU MP Bignum 库有一个高度优化的乘法实现。但是对于由几十个单词组成的数字，它只使用教科书乘法（最佳阈值很大程度上取决于机器）。事实上，GMP通过一系列最快的大小 X 算法进行转换。
于 2016-02-05T19:51:19.530 回答
-1
一种可能性 - O(n logn) 算法是递归的，但您可以迭代地编程 O(n^2)，并且您必须使用的编程语言不支持递归。
顺便说一句，“首选”在这里是相对的。如果数据集足够大，您可以通过使用您自己的堆栈变量来模拟递归，您可以在迭代实现的“递归”算法版本中操作该变量（我们必须在盖伊斯蒂尔的 CMU 的比较编程课程中进行该练习早些时候）。
于 2016-02-05T15:52:50.863 回答