随机化快速选择算法的时间复杂度理论分析与实验研究

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 随机化快速选择算法的时间复杂度理论分析与实验研究:http://www.lwfree.cn/jisuanjilunwen/20181126/26425.html
------分隔线----------------------------