对于无序的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的作用则被忽略。一般来说,最好情况和最坏情况发生的概率都比较低,人们最关心的是算法的平均性能,因此对这个问题有进一步深入研究的必要。
- 上一篇:环模制粒机技术国内外研究现状
- 下一篇:炸药爆轰管理传播国内外研究现状
-
-
-
-
-
-
-
大众媒体对公共政策制定的影响
酸性水汽提装置总汽提塔设计+CAD图纸
当代大学生慈善意识研究+文献综述
中考体育项目与体育教学合理结合的研究
java+mysql车辆管理系统的设计+源代码
河岸冲刷和泥沙淤积的监测国内外研究现状
电站锅炉暖风器设计任务书
杂拟谷盗体内共生菌沃尔...
十二层带中心支撑钢结构...
乳业同业并购式全产业链...