快速选择时间复杂度解释 [英] Quickselect time complexity explained

问题描述

来自 https://en.wikipedia.org/wiki/Quickselect 它说

"然而，与快速排序中的双向递归不同，快速选择只递归到一侧——它正在搜索的元素所在的一侧.这将平均复杂度从 O(n log n) 降低到 O(n))，最坏的情况是 O(n^2)."

"However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from O(n log n) to O(n), with a worst case of O(n^2)."

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

I dont understand how reducing to only looking at one side reduces average complexity to O(n)? Wouldnt it be more of O(N/2 log N) which is still O(N log N). And how is the worst case O(n^2)

推荐答案

n log(n) 暗示该算法查看所有 N 项 log(n) 次.但这不是 Quickselect 发生的事情.

n log(n) implies that the algorithm looks at all N items log(n) times. But that's not what's happening with Quickselect.

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

Let's say you're using Quickselect to pick the top 8 items in a list of 128. And by some miracle of random selection, the pivots you pick are always at the halfway point.

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

On the first iteration, the algorithm looks at all 128 items and partitions into two groups of 64 items each. The next iteration splits into two groups of 32 items each. Then 16, and then 8. The number of items examined is:

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

那个系列的总和永远不会达到 2*N.

The sum of that series will never reach 2*N.

最坏的情况是分区总是导致分区大小非常不平衡.考虑如果第一个分区只删除一个项目会发生什么.第二个只删除了一个，等等.结果是:

The worst case is that partitioning always results in very skewed partition sizes. Consider what would happen if the first partitioning only removed one item. And the second only removed one, etc. The result would be:

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

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

哪个是(n^2 + n)/2)，或者O(n^2).

Which is (n^2 + n)/2), or O(n^2).

这篇关于快速选择时间复杂度解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！