摘要线性时间选择算法是利用分治策略解决的经典算法。该算法的时间复杂度是 输入规模 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 线性时间选择问题的引出

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

上一篇:跟踪-学习-检测算法及其在视频中目标跟踪的应用
下一篇:基于余弦积分图像的快速非局部去噪方法及应用研究

多频激励下典型非线性系统的振动特性研究

计算机信息管理茬第三方...

浅析第四媒体广告【1780字】

第四方物流与电子商务协...

第三方物流与电子商务的整合模式【2442字】

第三方平台的电子商务分析【2704字】

第三方企业电子商务平台...

发酵米粉优势菌株的发酵特性研究

肢体语言在小学英语教学中的应用浅谈

大淘宝网的虚假交易研究

2021年什么行业赚钱,适合...

激光模拟训练器材国内外研究现状

新疆农林高校學生昆虫生...

日语论文中日酒文化对比研究

淮安市高校足球运动损伤问卷调查表

个案管理茬老年糖尿病患...

浅谈农村大气环境保护的制度构建【1868字】