Quickselect的平均运行时间 [英] Average Runtime of Quickselect

问题描述

维基百科指出quickselect算法（链接）的平均运行时间为O （N）。但是，我不能清楚地了解这是怎么如此。 （通过递推关系+掌握方法的使用）任何人都可以向我解释，如何平均运行时间为O（n）？

Wikipedia states that the average runtime of quickselect algorithm (Link) is O(n). However, I could not clearly understand how this is so. Could anyone explain to me (via recurrence relation + master method usage) as to how the average runtime is O(n)?

推荐答案

由于

我们已经知道哪个分区我们所需的元素位于

we already know which partition our desired element lies in.

我们不需要排序（做分区）的所有元素，而只是做我们需要的分区操作。

We do not need to sort (by doing partition on) all the elements, but only do operation on the partition we need.

由于在快速排序，我们要做的一半分区*，然后在半半，但这个时候，我们只需要做好下一轮分区中的一个单分区（一半）的两个，其中所述元件有望在于

As in quick sort, we have to do partition in halves *, and then in halves of a half, but this time, we only need to do the next round partition in one single partition (half) of the two where the element is expected to lie in.

这就像（不是很准确）

N + 1/2 N + 1/4 N + 1/8 N + .....＆LT; 2 N

n + 1/2 n + 1/4 n + 1/8 n + ..... < 2 n

所以这是O（n）。

<子>一半是为了方便起见，实际的分区不准确50％。

这篇关于Quickselect的平均运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！