【精品】算法分析大作业

《【精品】算法分析大作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录1.1背景和意义12.1设计的目的和意义22.2目标与总体方案22.3设计方法和内容22.3.1设计方法22.3.2设计内容32.4设计创新和关键技术52.4.1设计创新52.4.2关键技术62.5结论6致谢6参考文献6附录A源程序的清单71.1背景和意义算法分析是对一个算法需要多少计算吋间和存储空间作定量的分析。算法(Algorithm)是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构二程序，求解一个给定的可计算或可解的问题，不同的

2、人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。分析算法可以预测这一算法适合在什么样的环境屮有效地运行，对解决同一问题的不同算法的有效性作出比较。计算机科学及应用活动中，最有挑战性的困难往往就是算法分析。人们总是根据应用实践的具体需求，抽象出描述简单而严格的一般性计算问题，专门研究设计这些问题的求解算法。算法设计追求川较低的时间和空间复朵性，计算得到满足要求的解。在过去的算法设计实践中，人们针对不同领域的问题设计了许多巧夺天工的求解算法；已形成若干Z有效的算法

3、分析技术。而通过学习这门课程，我们学到了许多的算法思想。在一学期的学习Z后，我们就通过木次的课程设计来检验白我的学习情况。正文2.1设计的目的和意义课程设计口的是为学生提供了一•个既动手乂动脑，独立实践的机会，将课木上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学牛理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。课程设计的意思是培养学生运川所学课程的知识分析解决实际问题的能力；培养学生调查研究、杳阅技术文献、资料、手册以及编写技术文献的能力；通过课程设计，耍求学牛在指导

4、教师的指导下，独立完成设计课题的全部内容，包括：（1）通过调查研究和上机实习，收集和调查右关技术资料。（2）掌握课程设计的基本步骤和方法。（3）根据课题的要求进行上机实验调试。2.2目标与总体方案木次实验设计是内部排序问题，排序乂乂很多的方法，所以木程序川了switch来选择不不同点排序方法，用了While循环来判断是否退出排序程序，如果不退出则进行case中的—•项排序方法对随机产生的数据进行排序。所有的排序方法都在主函数中有一个入口，然后在每个排序的子函数中対升序和降序再进行一次选择。排序的每个模块的思路都差不多，只是每个排序方法的实现算法不同。某本的思

5、路都是随机产生一组无序的数据，然后用一中排序方法的升序或者降序对它进行排序，然后现实每个排序方法的排序过程。最后现实统计出来吋间和空间复杂度。该排序程序系统用的数据是通过数组进行存储的，先定义了数组的容量，然后随机对数组的每一个元素赋值。通过排序再把排序后的数据再存入数组中，显示也是通过for循环一个个显示数组中每一个数据元素值。2.3设计方法和内容2.3.1设计方法本次实验主要是实现多种排序的方法功能模块一：该模块实现的是直接插入排序方法，直接插入排序的皋木思想是：假设待排序的记录存储在数组R[l...n]屮，在排序的过程的某一时刻，R被划分成两个子区间和

6、R[i...n],其中，前一个为排好序的有序区，而后一个为无序区。开始时有序表中只有一个元素R11],无序区为Rl2....njo排序过程中，只需要每次从无序区中取岀第一个元素，不它插入到有序表区的适当位置，使Z成为新的有序区。依次这样经过次插入后，无序区为空，有序区中包含了全部n个元索，至此，排序完毕。功能模块二：该模块实现的是简单选择排序方法，直接插入排序的基本思想是：每次从待排序的无序区屮选择出关键字最人（最小）的记录，把该记录与该区屮的第一个记录交换位置。初始时,R[l...n]中选出最大或者故小的记录，将它与R[l]交换，R[l]为有序区；第二趟在

7、无序区R[2...n]中选出故大（最小）的记录与R[2]交换，此时R[l,2]为有序区;依次类推,做n-1趟排序后,区间R[1•…n]中记录递减（递增）有序。功能模块三：该模块实现的是堆排序方法，直接插入排序的棊本思想是：在排序过程中，将记录数组R[l...n]看成是一棵完全二叉树的顺序存储结构，利用完全二义数屮双亲结点和孩子结点之间的内在关系，在当前无序中选择关键字最人（最小）的记录。功能模块四：该模块实现的是冒泡排序方法，直接插入排序的基本思想是：通过相邻元索Z间的比较和交换，使排序关键字较人（较小）的元素逐渐从底部移向顶部，即从下标较大的元素移向下标较

8、小的元素。功能模块五：该模块实现的是快速排序方法，直