使用快速排序查找数组中第 k 个最小的项 =>预计运行时间? [英] Finding the kth smallest item in an array using quicksort => expected running time?

问题描述

如果我使用修改版的快速排序来查找数组中的第 k 个最小项，为什么预期运行时间为 O(n)(如 Programming Pearls 一书中所述)?

If I am using a modified version of quicksort to find the kth smallest item in an array, why is the expected running time O(n) (as stated by Programming Pearls book)?

我使用的算法执行以下操作:

The algorithm I'm using does the following:

1) Runs quick sort on the array
2) If k is > the correct location of pivot, then run quicksort on the 2nd half.
Otherwise run it on the first half.

我的印象是这需要 O(n * logn) 的工作量.

I was under the impression this would take O(n * logn) work.

推荐答案

这个链接，可能有助于理解随机快速选择的证明，http://pine.cs.yale.edu/pinewiki/QuickSelect,

This link, may help to understand the proof for randomized quick select, http://pine.cs.yale.edu/pinewiki/QuickSelect,

获取第 K 阶统计数据背后的想法是，选择一个主元，并按照快速排序的建议对数据进行分区，并找出要搜索的元素所在的分区.分区的复杂度为 O(n).分区后，您只需要选择一个结果分区进行进一步处理，不像快速排序，您必须同时处理两者.

Idea behind getting Kth order statistic is, select a pivot, and partition the data as suggested by quick sort and find out which partition the element being searched for lies in. Partitioning has the complexity of O(n). After partitioning, you need to pick, just one of resulting partition for further processing unlike quick sort, where you have to process both.

在下面的描述中，我不是想证明，而是想给出直观的想法来理解预期的复杂性，

In the below description, I am not trying to prove, but wanted to give intuitive thoughts to understand the expected complexity,

为了简单起见，让我们假设，在每次迭代中，pivot 将数组分成相等的两半，那么复杂度显然是 O(n)，如

For simplicity, let us assume, on every iteration, pivot splits the array in equal halves, then the complexity is clearly O(n), as

   n + (n/2) + (n/4) ... <= c.n, O(n)

为了直观的理解，得到一个最坏情况的分区，你必须在每次迭代中处理 (n-1) 个元素，概率仅为 (1/n).所以，无论如何，最坏情况的复杂度是 O(n^2).

For intuitive understanding, getting a worst case partitioning, where you would have to process (n-1) elements in every iteration happens with the probability of just (1/n). So, the worst case complexity is anyway, O(n^2).

无论如何，如果您想对预期的复杂性进行严格的证明，您可以访问所提供的链接.

Anyways, if you want a rigorous proof for expected complexity, you can go through the link, provided.

这篇关于使用快速排序查找数组中第 k 个最小的项 =>预计运行时间?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！