菜单
  
    对于无序的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的作用则被忽略。一般来说,最好情况和最坏情况发生的概率都比较低,人们最关心的是算法的平均性能,因此对这个问题有进一步深入研究的必要。
  1. 上一篇:环模制粒机技术国内外研究现状
  2. 下一篇:炸药爆轰管理传播国内外研究现状
  1. 曲柄滑块机构的研发现状和未来发展方向

  2. 液压试验台的国内外研究现状和发展趋势

  3. PLC的发展研究现状历史及趋势

  4. 混合动力汽车国内外研究现状和参考文献

  5. 内部EGR技术的研究现状

  6. 国内外对茉莉精油的研究现状

  7. 国内外城市的物流交通情况研究现状

  8. 大众媒体对公共政策制定的影响

  9. 酸性水汽提装置总汽提塔设计+CAD图纸

  10. 当代大学生慈善意识研究+文献综述

  11. 中考体育项目与体育教学合理结合的研究

  12. java+mysql车辆管理系统的设计+源代码

  13. 河岸冲刷和泥沙淤积的监测国内外研究现状

  14. 电站锅炉暖风器设计任务书

  15. 杂拟谷盗体内共生菌沃尔...

  16. 十二层带中心支撑钢结构...

  17. 乳业同业并购式全产业链...

  

About

751论文网手机版...

主页:http://www.751com.cn

关闭返回