线性查找第k小元素的算法设计分析与优化研究

菜单

摘要线性时间选择算法是利用分治策略解决的经典算法。该算法的时间复杂度是输入规模 n 的线性函数，其中线性函数的常系数取决于一个非常重要的参数，即分组的子序列长度。利用大量的实验数据通过递归思想和分治策略求解线性时间选择第 k 小元素问题，得出不同的子序列长度时复杂度因子的情况。在递归算法的基础上，给出一个基于映射方法对分组数据作快速排序的非递归线性选择算法，通过理论和实验分析了算法的时间复杂度，并且通过实验结果来验证理论分析的正确性。68465

毕业论文关键词线性时间选择算法时间复杂度递归非递归

Title Analysis and optimization of the algorithm design of linear time to find the first k small element

Abstract

Linear time selection algorithm is a classic algorithm using the pide and conquer strategy to solve. The algorithm's time complexity is a linear function of the size of the input of n, the constant coefficient of the linear function depends on a very important parameter, namely the length of the subsequence of the grouping.Through recursive thought and the pide and conquer strategy and use a lot of experimental data to solve the linear time to choose the first k elements of small problem, we can get the complexity of the situation when the different sub-factor sequence length. Given the subsequence length of the algorithm should be symmetric, so we only consider the length of the subsequence of odd number larger than 4.On the basis of the recursive algorithm, we present a non-recursive linear time algorithm based on mapping method for quick sort of packet data, we can obtain the time complexity of the algorithm through theoretical and experimental analysis and verify the correctness of the theoretical analysis via the experimental results .

Keywords linear time algorithm selection the time complexity of the algorithm recursive non-recursive

1 绪论 1

1.1 线性时间选择问题的引出 1

1.2 时间复杂度的概念 1

1.3 课题研究的意义 2

1.4 本文的结构 2

2 相关技术的研究 2

2.1 递归 2

2.2 分治 3

2.3 分治递推关系的解 4

2.4 分治策略的典型例子：二分搜索技术 5

2.5 基本排序 6

2.6 Hash 表 7

2.7 Matlab 中的直线拟合 8

3. 递归求解线性时间查找第 k 小个元素 9

3.1 思路及实现 9

3.2 选择算法的时间复杂度分析 11

3.3 实验验证 14

4.非递归的线性选择算法 22

4.1 映射排序 22

4.2 非递归选择算法 24

结论 28

致谢 29

参考文献 30

1 绪论

1.1 线性时间选择问题的引出

算法是计算机学科的核心概念，也被誉为计算学科的灵魂。早期，人们日常生活中遇到各种各样的问题，能否用一种有效的过程来求解问题受到广泛的关注。那时，人们的注意力是放在问题是否可解上。随着数字计算机出现以后，人们对于可解问题的钻研要求越来越多。起初人们满足于一个简单的程序能够在它需要的时间内求解一个特定的问题，而不考虑资源量。而随着社会的发展，产生和需求的数据量越来越大，由于有限的可用资源和开发复杂算法的要求，以前只专注于问题是否可解的算法已经无法满足需求，因此需要提出尽可能少使用资源的有效算法。