随机化快速选择算法的时间复杂度理论分析与实验研究
时间:2018-11-26 11:18 来源:毕业论文 作者:毕业论文 点击:次
| 摘要算法是计算机科学的灵魂，算法时间复杂度分析在算法学科中的地位举足轻重，对于算法设计、算法分析与优化乃至实际工程计算都起着巨大的推动作用。查找是科学研究与工程计算中的重要基本操作，快速选择算法(Quickselect)是查找操作的有力工具，能在线性时间内从大量的无序数据中查找到第k小元素，遗憾的是其时间复杂度的精确度量仍然存在一定的争议。随机化快速选择算法虽然能够更快地解决同样的查找问题，但该算法的时间复杂度仍然没有被透彻地研究。30615 本文以上述两种算法为研究对象，通过对快速选择算法时间复杂度波形图的观察，以及通过对比实验的分析，发现其中的一些规律，研究了子序列长度对快速选择算法时间复杂度的影响。通过数学分析得到随机化快速选择算法的平均时间复杂度的理论紧上界，实验结果完全吻合这个理论分析结果。最后对研究工作进行总结归纳，得出了一些有意义的结论。这些结论是对教材有关内容的补充、深化和推广，也为相关的工程计算和应用研究提供了一定的理论支撑作用。 关键词 随机化的快速选择算法 快速选择算法 时间复杂度 毕业论文设计说明书外文摘要 Title Study on the Time Complexity Analysis with Experiments of Both Quickselect Algorithm and its Randomized Counterpart Abstract 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. Search is the important and fundamental operation in scientific research and engineering computation, and Quickselect algorithm is a powerful tool for the search operation, which can find the k-th smallest element in linear time from a large number of unordered data. Unfortunately, there are still some disputes in the precise measurement of its time complexity. The randomized fast selection algorithm can solve the same problem more quickly, but the time complexity of the algorithm is still not studied thoroughly. In this paper, we study two algorithm mentioned above. Firstly, by observing the graph of the time complexity for Quickselect and the analysis of the contrast experiments, we find some of the rules. Secondly, we study the effect of the length of the sub sequences on the time complexity of the Quickselect. Thirdly, we obtain the tight upper bound of the average time complexity of randomized Quickselect algorithm by theoretical analysis, and we use specific experiments to validate it. Finally we conclude and make some meaningful conclusion. These conclusions are the supplement, deepening and generalization of the related contents in textbook, providing some theoretical support for the relevant engineering calculation and application. Keywords Randomized Quickselect Quickselect Time Complexity 目 次 1 引言 1 1.1 选题背景与研究意义 1 1.2 算法思想与策略评述 2 1.3 国内外的研究现状 3 1.4 本文所做的工作及贡献 3 2 算法与时间复杂度分析 5 2.1 快速选择算法 5 2.2 随机化的选择算法 8 2.2.1 最坏时间复杂度 9 2.2.2 最好时间复杂度 9 2.2.3 期望时间复杂度 10 3 研究目标和实验设计 15 3.1 编程语言与计算平台 15 3.2 研究目标 15 3.2.1 快速选择算法 15 (责任编辑：qin) |