菜单
  

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

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

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

  2. MAYA+Unity次世代第一人称射击游戏设计与制作

  3. 高光谱遥感图像线性混合像元分解方法研究

  4. asp.net简易第三方微信公众平台管理系统设计

  5. 基于java的第三人称射击游戏的设计与实现

  6. jsp+mysql第三方物流管理信息系统的设计与实现

  7. jsp房地产信息网设计

  8. java+mysql车辆管理系统的设计+源代码

  9. 杂拟谷盗体内共生菌沃尔...

  10. 十二层带中心支撑钢结构...

  11. 酸性水汽提装置总汽提塔设计+CAD图纸

  12. 中考体育项目与体育教学合理结合的研究

  13. 河岸冲刷和泥沙淤积的监测国内外研究现状

  14. 当代大学生慈善意识研究+文献综述

  15. 大众媒体对公共政策制定的影响

  16. 乳业同业并购式全产业链...

  17. 电站锅炉暖风器设计任务书

  

About

751论文网手机版...

主页:http://www.751com.cn

关闭返回