关于经典SELECT顺序统计算法阈值与分组规则的疑问

问题1解答 #

• 设置|S| < 50是工程层面的常数优化，不是算法正确性的必要条件。小数据集下直接调用排序的常数开销远低于递归拆分、计算中位数、划分子集的开销，50是兼顾性能的经验阈值，换成30、100这类固定常数都可以。
• 当|S| > 50时算法完全可以正常运行，这个阈值只影响实际运行速度，不影响逻辑正确性和渐近时间复杂度，哪怕把阈值改成1（也就是所有规模都走递归分支），算法依然能正确输出结果，只是实际运行会慢很多。

问题2解答 #

• 选择每5个元素一组的核心目的是保证算法最坏情况下时间复杂度为O(n)。5是满足线性复杂度要求的最小奇数分组大小：5个一组时，每次选出的中位数的中位数m，至少有3/10的元素严格小于它、3/10的元素严格大于它，因此单次递归的子问题最大规模不超过7n/10，加上找中位数的递归规模是n/5，递推式T(n) ≤ T(n/5) + T(7n/10) + O(n)的解为O(n)，符合线性要求。同时5是奇数，每组找中位数不需要额外处理上下中位数的选择问题，排序5个元素的常数开销也很低。
• 改为每6个一组是可行的，依然能保证最坏O(n)的时间复杂度：6个一组时递推式为T(n) ≤ T(n/6) + T(2n/3) + O(n)，子问题规模系数和为1/6 + 2/3 = 5/6 < 1，解出来依然是线性的，只是每组排序和中位数计算的常数开销比5个一组更高，实际性能略差。
• 改为每4个一组不可行，无法保证最坏线性复杂度：4个一组时，子问题规模系数和为1/4 + 3/4 = 1，递推式的解为O(n log n)，失去了原算法最坏线性的核心优势。

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