-
对于无序的n个元素序列，快速选择算法先将该集合中的元素每5个分为一组，将每组元素进行排序，找出每组元素的中项，所有的中项的集合为M，然后令基准元素mm等于集合M的中项。在此基础上进行递归操作，直到找到我们所需要找的元素。可以证明[1]快速选择算法的时间复杂度C(n)满足（详细证明见2.1节）30615
- 上一篇：环模制粒机技术国内外研究现状
- 下一篇：炸药爆轰管理传播国内外研究现状
其中c是问题规模足够小时的时间复杂度。可以解得C(n)≤20cn。虽然说快速选择算法的时间复杂度为线性解，但是其线性解的常系数20c不确定，并且从形式上来推测也偏大。另外，子序列长度划设定为5，这种做法究竟是否能得到最好的结果，若子序列的长度划分为5个，7个，9个...等，这样做，对时间复杂度的影响上到底有多大，这方面的研究及参考文献也相对欠缺。
另一方面，对于随机化的选择算法，其基本原理和快速选择算法相同，只是在寻找基准元素上有差异，它利用随机算法来生成基准元素。尽我们所知，目前对该算法的时间复杂度研究文献比较少，文献[1]仅仅给出如下几条结论：论文网
1） 算法的最坏时间复杂度为Θ(n2)，并描述了这种最坏情况什么时候可能发生。
2） 算法的最好时间复杂度为C(n)≥n，但是并未明确指出这种最好情况什么时候发生。
3） 给出了算法的期望（数学平均）时间复杂度，证明了该算法的期望时间复杂度函数的上界，即C(n)<4n（详细证明见2.2节）。
通过深入研究，我们认为：
1) 算法的最坏时间复杂度为Θ(n2)，这个结论并无争议，但这仅仅是理论上存在的一种可能，这种最坏情况什么时候可能发生，实际发生的概率如何，值得进一步分析研究。
2) 算法的最好时间复杂度为C(n)=n，应该指出这种情况在什么时候能够发生。
3) 算法的期望时间复杂度为C(n)≤4n的理论表达式对问题的刻画比较粗略，仅仅反映了问题的输入规模n对算法复杂度的影响，而算法的另一个重要参数k的作用则被忽略。一般来说，最好情况和最坏情况发生的概率都比较低，人们最关心的是算法的平均性能，因此对这个问题有进一步深入研究的必要。