0

我们可以在线性时间内对未排序的实数数组进行排序吗？这就是我的想法：

给定一个大小为 n 的未排序数组：

  • 使用选择算法找出sqrt(n)^th元素（称为 x）：O(n)
  • 找出比 x 小的元素和比 x 大的元素并形成 2 个数组：O(n)
  • 将两个数组分别排序： O(sqrt(n)log(sqrt(n))) = O(n) as log(n) < sqrt(n)

所以整个算法是O(n)

我知道下限是 nlog(n)。我究竟做错了什么？

4

0 回答 0