随机化快速选择算法时间复杂度研究

Research on Time Complexity of Randomized Quickselect Algorithm

算法是计算机科学的灵魂,算法时间复杂度分析在算法学科中的地位举足轻重,对于算法设计、算法分析与优化乃至实际工程计算都起着巨大的推动作用。该文通过数学分析得到随机化快速选择算法的平均时间复杂度理论紧上界,并进一步通过实验验证该理论。最后对研究工作进行总结归纳,得出了一些有意义的结论,为相关的工程计算和应用研究提供了一定的理论支撑作用。

Algorithm is the soul of the computer science,so study on the time complexity plays an important role in algorithm subject,significantly promoting the research of the algorithm design,algorithm analysis and optimization as well as actual engineering. The tight upper bound of the average time complexity of randomized Quickselect algorithm is obtained by theoretical analysis,and specific experiments are used to validate it. Finally some meaningful conclusion are concluded,providing some theoretical support for the relevant engineering calculation and application.