法做到像递归那样有回溯的过程。
后来我和同学上自习的时候,她用树来记录分治的过程,下面是对 10 个元素进行排序所要用到的树。
只要对树进行后序遍历,遍历时对该节点所记录的区间的元素进行归并,当整棵树遍历完成时,元素就是有序的了。
实际上递归的归并排序的调用以及回溯过程隐式的建立并遍历了这样的一棵树。
不过这样做还是有些麻烦,后来我们想到了另一种办法。
我们先让两个两个一组进行归并,再四个四个一组进行归并,再八个八个一组归并… …. 由于问题的规模并不总是 2 的 k(k 为自然数)次方,因此要对末尾的一组元素进行单独考虑。
由于只有当归并的两个子区间是有序的,归并得到的序列才会有序,因此需要保证最后一组元素始终有序。
可以采用递归的方法证明。
当第一次归并时,每一组元素的个数只有一个,因此最后一组序列必然是已序的,因为它只包含一个元素。
第 k 此归并,每一组包含 pow 2 k – 1 个元素,假设此时最后一组元素仍是有序的。
于是在第 k 1 次归并时,可能出项两种情况: (1) 最后一组元素没有可以与之归并的,它将保持不变,因此仍将有序。
(2) 最后一组元素可以与之前一组元素归并,由于两组都有序,归并得到的新组 也将有序。
即第 k 1 次归并之后,最后一组元素仍将有序。
因此,无论何时,最后一组元素都 是有序的。
非递归程序的算法 // 归并函数 int length source.size // 记录数组元素的长度 int size 1 // 记录一组包含多少元素,初始时,一组有一个元素 int i 0 // 标记量,记录当前归并到何处 While size lt length // 当 size 小于数组长度时将一直循环 While i 2 size lt length // 还有两组可以归并时 归并 i i size , i size i 2 size 区间的元素 i 2 size // 归并标记往后移两组 If i size lt length // 判断最后一组元素是否可与前一组归并 归并 i i size, i size length i 0 // 归并标记移回到开始 size 2 // 每组包含的元素数量加倍 算法的时间复杂性 易知 merge函数的时间复杂性与要归并的元素数量成正比。
假定算法的时间复 杂性为 Tn,为了方便分析,假设问题的规模为 pow 2 n ,于是有: T pow 2 n 2 pow 2 n – 1 pow 2 2 pow 2 n – 2 pow 2 3 pow 2 n – 3 … … pow 2 n – 1 2 pow 2 n n – 1 因此易得 T n n log 2 n - 1 ≈ n log 2 n 故算法的复杂性为 On n logn。
算法的时间大部分花在归并操作上,而不论归并的两个子区间元素顺序如何,归 并都是要遍历两个子区间,并且复杂度 On n,因此算法的最坏、最好以及平均时 间复杂度都是 n log n 。
算法的空间复杂性 该算法只需要一个临时数组用于存储排序结果,因此时间复杂度为 On。
三、 主要仪器设备及耗材 PC 一台,VC Express 2008第二部分:实验调试与结果分析(可加页)一、调试过程(包括调试方法描述、实验数据记录,实验现象记录,实验过程发现的问题等) 这次试验有两个难点,一个是设计一个非递归的归并排序算法,另一个是编程的小错误,我将 source 数组的元素排好序放到 dest 数组之后,没有将其拷贝回 source 数组,导致合并之后 source 的一个分组内元素并不是有序排列的。
二、实验结果及分析(包括结果描述、实验现象分析、影响因素讨论、综合分 析和结论等)程序源代码includeltiostreamgtincludeltvectorgtusing namespace stdvoid merge vectorltintgt ampsource vectorltintgt ampdest int begA int begB int endB int k begA i begA endA begB while begA endA ampamp begB endB if sourcebegA gt sourcebegB destk sourcebegB else destk sourcebegA while begA endA destk sourcebegA while begB endB destk sourcebegB for i endB i sourcei destivoid mergeSort vectorltintgt ampsource vectorltintgt dest int i 0 size 1 length source.size dest.resize length while size lt length while i 2 size lt length merge source dest i i size i 2 size i 2 size if i size lt length merge source dest i i size length i 0 size 2 int main int temp vectorltintgt source cout ltlt quot请输入要排序的数组:quot ltlt endl while cin gtgt temp source.push_back temp mergeSort source cout ltlt quot排序结果如下:quot ltlt endl for int i 0 i source.size i cout ltlt sourcei ltlt cout ltlt endl system quotpausequot return 0运行结果截图 截图(1) 截图(2) 截图(3)三、 实验小结、建议及体会 本次试验对递归的归并排序有了更深的理解,递归的归并排序有划分和归并两个过程。
实际上算法的递归调用以及回溯就是隐式的建立一棵树,该树记录了区间是如何被划分的。
归并相当于处理该树的节点并,它将两个划分的区间进行合并,得到一个新的有序区间。
而回溯相当于返回节点的父节点。
递归利用栈的出栈和入栈可以动态的建立和销毁树的节点,它最多只需要花费记录一条到树底端的路径所需的栈空间,其空间复杂性以及时间复杂性是非常高的,缺点是递归的消耗比循环多。
非递归的归并排序省去了动态的划分区间的过程,而是让相邻的一组区间归并,然后让组的容量翻倍,它需要单独考虑最后一组元素的特殊情况。
一般来讲非递归的程序都比完成同样任务的非递归的程序要复杂的多,不过非递归的归并排序在这里也出奇的精简巧妙,乍看起来感觉不可思议。
实验课程名称: 货郎担问题实验项目名称 货郎担问题 实验成绩实验者 桂江亨 专业班级 软件 Sy1001 组别同组者 实验日期 年 月 日第一部分:实验分析与设计(可加页)一、实验内容描述(问题域描述) 1.实验描述:将动态规划算法应用于货郎担问题和工程中的资金分配问题的求解, 设计出高效的算法。
本实验是综合型、设计型实验,在实验中需要综合运用《离散数 《数据结构》中的集合、队列、树; 学》中的数理逻辑、图; 《程序设计》中的数组、 条件控制、循环控制、指针、结构体和《算法设计与分析》中的动态规划算法、多段 图、以及计算时间的渐进表示和算法的时间复杂性分析等等方面的知识。
2.实验内容: 利用动态规划思想,求货郎担问题,并利用任何一种语言,在计算机上实现,同时进 行时间复杂性分析。
3. 实验要求 用 首先要对实验内容进行描述, SPARK 语言设计算法,然后 C/C或 JAVA 语编写程 序对算法实现,同时用具用代表性的数据给 3 组典型输入数据进行测试,实验后, 进行实验总结,描述设计过程步骤及各步骤含义。
其中实验内容 1)还要求对算法的 时间复杂性进行分析,实验内容 2)还要求写出动态规划递推关系式。
二、实验基本原理与设计(包括实验方案设计,实验手段的确定,试验步骤等,用硬件逻辑或者算法描述) 货郎担问题简述,卖货郎从城市 0 出发,途径1,2,… … n n 个城市,并最终 返回城市 0。
为了节省路费,货郎需要选择花费最短的一条路径周游这些城市。
假设最终是从 k 城市返回城市 0,问题转化为求从 k 城市出发经过集合 Ci – k 1 lt i lt n 返回城市 0 的最短路径。
假设用 D k S 表示从城市 k 出发,经过城市 S 集合 返回城市 0 的最短路径问题。
那么有 Dk S min dist k r D r S – r r ∈ S Dr dist r 0 因此货郎担问题等价于 TSPPro 0 S min dist 0 k D k
上一篇:
并行编程模式
下一篇:
英语论文网([网学网]):英语专业本科生毕业论文写作