快速选择算法的时间复杂度解释

Question

快速选择算法的时间复杂度解释

algorithmtime-complexityquickselect

17

从https://zh.wikipedia.org/wiki/快速选择算法中可以看到：

“然而，与快速排序递归进入两侧不同，快速选择仅递归进入一侧——具有所搜索元素的那一侧。这将平均复杂度从O(n log n)降低到O(n)，最坏情况下为O(n^2)。”

我不明白为什么只查看一侧会将平均复杂度降低到O(n)？难道不应该是O(N/2 log N)吗，这仍然是O(N log N)。另外，最坏情况如何会是O(n^2)？

- ealeon

4个回答

20

一开始，当我看到平均时间复杂度为O(n)，而我们每次都将列表分成两半（如二分查找或快速排序）时，我感到非常矛盾。为了证明只看一边可以将平均运行时间复杂度从O(n log n)降低到O(n)，让我们比较快速排序（双侧）和快速选择（单侧）的时间复杂度递归关系。

快速排序：

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)

我希望这能让你明白为什么只看一个方面会有所不同！

- Aron Vischjager

19

一张图片胜过千言万语：

这种类型的序列求和会无限接近于1，但不等于1。

- JasonLi

0

它的复杂度几乎是 Θ(N)(平均 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获取更多详细信息。

- aeof

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Mischel · Accepted Answer

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)。