9

从https://en.wikipedia.org/wiki/Quickselect它说

“然而，不像在快速排序中那样递归到两边，快速选择只递归到一侧——它正在搜索的元素所在的一侧。这将平均复杂度从 O(n log n) 降低到 O(n)，与O(n^2) 的最坏情况。”

我不明白减少到只看一侧如何将平均复杂度降低到 O(n)？会不会更多 O(N/2 log N) 仍然是 O(N log N)。最坏的情况如何 O(n^2)

4

4 回答 4

29

n log(n)意味着该算法查看所有 N 个项目 log(n) 次。但这不是 Quickselect 发生的情况。

假设您正在使用 Quickselect 在 128 个列表中选择前 8 个项目。通过随机选择的一些奇迹，您选择的枢轴始终位于中间点。

在第一次迭代中，算法查看所有 128 个项目并将其分成两组，每组 64 个项目。下一次迭代分成两组，每组 32 个项目。然后是 16，然后是 8。检查的项目数是：

N + N/2 + N/4 + N/8 + N/16

该系列的总和永远不会达到 2*N。

最坏的情况是分区总是导致分区大小非常倾斜。考虑如果第一个分区只删除一个项目会发生什么。第二个只删除了一个，依此类推。结果将是：

N + (N-1) + (N-2) ...

即(n^2 + n)/2), 或 O(n^2)。

于 2019-07-08T19:37:06.610 回答
14

一张价值一百行的图片：

这种序列的和将无限接近1但不等于1。

于 2020-09-15T20:35:21.703 回答
10

当我读到平均时间复杂度为 O(n) 而我们每次将列表分成两半（如二进制搜索或快速排序）时，我也感到非常矛盾。为了证明只看一侧将平均运行时复杂度从 O(n log n) 降低到 O(n)，让我们比较一下快速排序（2 面）和快速选择（1 面）的时间复杂度递归关系。

快速排序：

T(n) = n + 2T(n/2)
     = n + 2(n/2 + 2T(n/4))
     = n + 2(n/2) + 4T(n/4)
     = n + 2(n/2) + 4(n/4) + ... + n(n/n)
     = 2^0(n/2^0) + 2^1(n/2^1) + ... + 2^log2(n)(n/2^log2(n))
     = n (log2(n) + 1)      (since we are adding n to itself log2 + 1 times)

快速选择：

 T(n) = n + T(n/2)
      = n + n/2 + T(n/4)
      = n + n/2 + n/4 + ... n/n
      = n(1 + 1/2 + 1/4 + ... + 1/2^log2(n))
      = n (1/(1-(1/2))) = 2n                           (by geometric series)

我希望这能说服你为什么看一侧会有所不同！

于 2021-04-24T17:28:52.943 回答
0

它的复杂度几乎是Θ(N)(Everage O(N))。

假设目标索引为 1，这意味着我们要找到最小元素：

  • 第一个循环：检查整个 [1, N] 和分区，近 N 次操作。
  • 第二个循环：检查整个 [1, x] 和分区，近 N/2 次操作。
  • 第三个循环：检查整个 [1, y] 和分区，近 N/2 次操作。
  • ...

最终循环：检查整个 [1, 1]，arr[1] 是我们的目标，1 操作。

因此，复杂度约为：

T = T(N + N/2 + N/4 + ... + 1) 
     = T(1*(1-2^(logN))*(1-2)) 
     = T(2^(logN) - 1) 
     = Θ(N)

这个表达式可能太简单了，但希望它可以帮助你。顺便说一下，这是快速选择的平均复杂度，因为快速排序/快速选择的性能可能会因为列表值分布和目标索引而波动。您可以查看https://en.wikipedia.org/wiki/Quickselect了解更多详情。

于 2021-11-10T03:50:38.833 回答