algorithm - Quickselect 的平均运行时间

Question

维基百科指出快速选择算法 (Link) 的平均运行时间为 O(n)。但是，我无法清楚地理解这是怎么回事。任何人都可以向我解释(通过递归关系 + 主方法的使用)平均运行时间是 O(n) 吗？

Answer 1

因为

we already know which partition our desired element lies in.

我们不需要对所有元素进行排序(通过分区)，而只对我们需要的分区进行操作。

---

和快速排序一样，我们要先对半*，再对半对半进行分区，但这次只需要在一个单分区中进行下一轮分区(元素预期位于的两个中的一半。

好像(不是很准确)

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

所以它是 O(n)。

_{Half是为了方便，实际的划分不是精确的50%。}