algorithm - 对数组中最小的 n/logn 元素进行排序

Question

如何在 O(n) 中对数组中最小的 n/(log n) 元素进行排序？

我知道如何对最小的 k 元素进行排序是 O(n+k*log k)，但是如何将其用于我的问题？

Answer 1

如果 k=n/(log n)，那么使用您知道的算法将花费 O(n+(n/(log n))*log(n/(log n)))，并且由于 n > n/(log n), log n > log(n/(log n))，因此这也是 O(n)。