O(n log n) 与 O(log n) 有何不同？
How is O(n log n) different then O(log n)?
研究大 O 表示法，我理解 O(log n) 作为二进制搜索和 O(n log n) 作为快速排序的概念。
任何人都可以用通俗的话说 runtime 这两者之间的主要区别是什么？为什么会这样？
直觉上它们似乎具有相似的相关性
基本上：N 的一个因子。
二分查找只涉及少量元素。如果有 10 亿个元素，二分查找只会涉及其中的 ~30 个。
快速排序会触及每个元素，但次数很少。如果有 10 亿个元素，快速排序会触及 所有 个元素，大约 30 次：总共约 300 亿次触及。
在简单的术语和可视化上，它们在排序算法上有点相同，但是快速排序因为 O(n log n) 在某些情况下有缺陷，快速排序大多数情况是 log n，但在特殊情况下是 n²，这就是为什么 n 在 logn。所以快速排序对于少量排序是非常好的，但是对于 millions/billions 它不是，更好地使用 Merge Sort 进行这种排序。
看看 Log(n) 是如何平坦的（与其他函数相比，不是字面意思，而是比喻），而 nLog(n) 已经超过 600 的值 n = 100。这就是它们的不同之处。
研究大 O 表示法，我理解 O(log n) 作为二进制搜索和 O(n log n) 作为快速排序的概念。
任何人都可以用通俗的话说 runtime 这两者之间的主要区别是什么？为什么会这样？
直觉上它们似乎具有相似的相关性
基本上：N 的一个因子。
二分查找只涉及少量元素。如果有 10 亿个元素，二分查找只会涉及其中的 ~30 个。
快速排序会触及每个元素，但次数很少。如果有 10 亿个元素，快速排序会触及 所有 个元素，大约 30 次：总共约 300 亿次触及。
在简单的术语和可视化上，它们在排序算法上有点相同，但是快速排序因为 O(n log n) 在某些情况下有缺陷，快速排序大多数情况是 log n，但在特殊情况下是 n²，这就是为什么 n 在 logn。所以快速排序对于少量排序是非常好的，但是对于 millions/billions 它不是，更好地使用 Merge Sort 进行这种排序。
看看 Log(n) 是如何平坦的（与其他函数相比，不是字面意思，而是比喻），而 nLog(n) 已经超过 600 的值 n = 100。这就是它们的不同之处。