内省选择（introselect）最坏时间复杂度如何达到O(n)？

introselect 最坏O(n)复杂度实现相关问题解答 #

如何实现最坏时间复杂度为O(n)的introselect

introselect是快速选择和最坏线性选择算法的混合实现，要保证最坏O(n)复杂度，核心是避免切换到O(nlgn)级别的算法，正确的实现逻辑如下：

• 初始阶段执行普通快速选择：每次选择枢轴执行partition_pivot操作，将数组分区后递归处理目标元素所在的子区间，快速选择平均复杂度极低，是实际运行时的主要执行路径
• 设置递归深度阈值：当快速选择的递归深度超过预设阈值时，判定当前遇到了枢轴选择的最坏情况，立刻切换到中位数的中位数算法来完成后续的选择操作，中位数的中位数最坏复杂度为O(n)，可以保证整体复杂度不会劣化到O(nlgn)
  注意不要像部分旧实现那样切换到堆排序，堆排序本身最坏复杂度就是O(nlgn)，切换后自然会导致整体复杂度不达标。

用常数k替代2lg(n)作为阈值是否可以得到O(n)复杂度

是的，只要k是固定常数，不管具体取值多大，整体最坏时间复杂度都为O(n)：

• 前k次partition_pivot操作每次处理的序列长度依次减半，总操作量为 n + n/2 + n/4 + ... + n/2^k < 2n，属于线性量级
• 超过阈值切换到中位数的中位数后，剩余子序列长度最多为n/2^k，中位数的中位数处理该子序列的复杂度为O(n/2^k)，同样属于线性量级
  两者相加整体最坏复杂度仍然是O(n)，和k的具体取值无关。

实用的常数k取值

工业界实现的常用k取值范围在15~30之间，不同场景的典型取值如下：

• 20：这是绝大多数标准库的默认取值，比如GNU libstdc++、LLVM libc++中的nth_element函数（底层基于introselect实现）都用20作为阈值，兼顾了普通场景的性能和最坏场景的复杂度
• 16：嵌入式、低延迟场景常用更小的16，减少最坏场景下的切换开销
• 30：对性能波动容忍度较高的场景可以用30，尽量延长快速选择的执行时间，毕竟快速选择的常数开销远低于中位数的中位数，绝大多数场景下不会触发切换，运行效率更高。

内容的提问来源于stack exchange，提问作者Voyager