毕业论文

当前位置: 毕业论文 > 计算机论文 >

线性对数阶排序算法的时间复杂度实验对比研究

时间:2017-12-06 20:03来源:毕业论文
堆排序以及归并排序(分为递归与非递归两种)算法复杂度的阶的系数,作为其复杂度比较精确的表示,从理论和实践两重意义上解决了“这几种O(nlogn)的排序算法之间孰快孰慢”的问题
摘要算法时间复杂度的传统分析方法是求其期望平均,虽然这种分析方法具有更多的理论指导意义,但往往只能得到时间复杂度函数的阶,不便于细致地比较一些同阶的函数,因而对实际工程的意义实在有限。众所周知,算法的时间复杂度与问题的规模和输入实例有关。与理论分析方法相比,实验方法是计算比较算法的绝对运行时间,这种方法虽然对实际工程问题具有显著的应用价值,但遗憾的是对理论分析却不具有指导意义,因为算法具体实例化为程序运行时,计算时间还跟软硬件平台甚至编程技巧有关。 本课题的创新点是创造性地将上述两种方法的优点结合起来,利用数学理论分析的方法,得出或估计出算法复杂度的阶的精确表示(即尽量给出阶函数的系数的较为精确的表示),然后通过数值仿真计算的方法,通过大量的实例计算、阶函数拟合与比较分析的方法,细致入微地比较研究不同算法的时间复杂度,用这种方法,我们研究了几种线性对数阶的排序算法,即经典快速排序,改进的快速排序,堆排序以及归并排序(分为递归与非递归两种)算法复杂度的阶的系数,作为其复杂度比较精确的表示,从理论和实践两重意义上解决了“这几种O(nlogn)的排序算法之间孰快孰慢”的问题,为理论教学提供有力的依据,也为实际工程计算提供一定的借鉴作用。 16222
关键词 : 理论分析, 数值仿真, 快速排序, 堆排序, 归并排序。
毕业设计说明书(论文)外文摘要
Title    Experimental comparative study of time complexity of                     源自六;维,论/文.网*加7位QQ324`9114 www.lwfree.cn
 several lineal logarithmic order sorting algorithm                                                
Abstract
Traditional methods of obtaining the time complexity is seeking its expected average , although this method of analysis has more theoretical significance , but often only get the order of the time complexity , not easy to compare some of the same order meticulous function , thus the significance of the actual project is very limited. As we all know , the algorithm time complexity has the relation with the scale of the problem and the relevant instances . Compared with the theoretical analysis,the experimental method is to calculate the absolute comparison algorithm running time , although this method has significant value for practical engineering problems , but unfortunately not on the theoretical analysis , because the algorithm specific instantiation when the program is running , the calculation time even kind enough programming skills related hardware and software platforms . The innovation of this project is to creatively advantage of combining the two methods , the use of mathematical methods of theoretical analysis , draw or estimate accurately represents the order of complexity of the algorithm (try to give a more accurate order function ) , and then by numerical simulation method by calculating a large number of instances , the order function fitting and methods of comparative analysis , nuanced comparative study of different time complexity of the algorithm , using this method , we studied several linear order of sorting algorithms , namely classic quick sort , improved quick sort , heap sort and merge sort ( recursive and non-recursive included ) order coefficient complexity of the algorithm , as its complexity is relatively accurate representation , from the theoretical and practical significance to solve the problem" what is fast and what is slow between these sorting algorrithm of the order of O(nlogn)" , providing a strong basis for the theory of teaching , but also provide some reference for practical engineering calculations. 线性对数阶排序算法的时间复杂度实验对比研究:http://www.lwfree.cn/jisuanjilunwen/20171206/17487.html
------分隔线----------------------------
推荐内容