introselect 的最差时间复杂度怎么变成了`O(n)`？

Question

维基百科 introselect 说最差的时间复杂度是 O(n)。

但是，参考这个答案，，一些 introselect 的实现运行 2lg(n) 次 partition_pivot，其最差时间复杂度为 O(nlg(n))。不管你用堆排序的medians_of_medians算法，时间复杂度已经是O(nlg(n)).

最坏的时候如何实现O(n) introselect？ 如果我们使用常量 k 而不是 2lg(n)。我们可以说时间是 O(n) 吗？你能给我一些实用的k选择吗（必须是常数）？

Answer 1

However, refer [sic] to this answer, , some implementation of introselect runs 2lg(n) partition_pivot

如评论中所述，该实现是 named introselect，但实际上并未实现 introselect algorithm.

How to achieve a worst time O(n) introselect?

您使用恒定数量的分区执行快速选择，或者要求分区高度不平衡最多恒定次数，如果不在这些限制内完成，您切换到 median of medians 算法。

请注意，最近还有 A. Alexandrescu 的 QuickSelectAdaptive algorithm，其中详细介绍了如何实施确定性线性时间选择。