algorithm - O(n log n) 算法是否总是优于所有 O(n^2) 算法？

Question

当试图正确理解 Big-O 时，我想知道 O(n log n) 算法是否总是优于所有 O(n^2) 算法。

有没有O(n^2) 更好的特定情况？

我读过很多次排序，例如，当数据几乎排序时，像冒泡排序这样的 O(n^2) 算法可以特别快，所以它会比O(n log n) 算法，例如合并排序，在这种情况下？

Answer 1

不，O(n log n) 算法并不总是比O(n^2) 算法好。大 O 表示法描述了算法渐近行为的上限，即 n 趋于无穷大。

在这个定义中你必须考虑一些方面:

1. Big-O 表示法是算法复杂度的上限，这意味着对于某些输入(例如您提到的排序算法)，具有最差 Big-O 复杂度的算法实际上可能表现更好(冒泡排序在 O(n) 对于已经排序的数组，而合并排序和快速排序总是至少需要 O(n log n));
2. Big-O 表示法仅描述复杂性类别，隐藏了在实际情况下可能相关的所有常量因素。例如，O(n) 类中具有复杂度 1000000 x 的算法比具有复杂度 0.5 x^2 的算法表现最差(class O(n^2)) 对于小于 2000000 的输入。基本上 Big-O 符号告诉你对于足够大的输入 n，O(n) 算法将比 O(n^2) 表现更好，但如果您使用小输入，您可能仍然更喜欢后一种解决方案。