算法分析与设计课程实验报告

《算法分析与设计课程实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计课程实验报告班级：131213学号：13121XXX姓名：XXX指导老师：邓凡目录算法分析与设计课程实验报告1实验一排序11.课本练习2.3-712.实现优先队列23.快速排序24.第k大元素3实验二动态规划41.矩阵链乘42.最长公共子序列53.最长公共子串74.最大和95.最短路径10实验三贪心策略111.背包问题112.任务调度143.单源点最短路径154.任意两点间最短路径16实验四回溯法181.0-1背包问题182.8-Queen问题21实验一排序1.课本练习2.3-7(1)问题描述描述一个运行时间为

2、(nlgn)的算法，给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好是x的元素。(2)问题分析该问题首先要进行排序，然后用二分查找法判断S中是否存在两个其和刚好是x的元素，因为时间复杂度为(nlgn)，所以可以采用归并排序。(3)算法分析归并排序的思想是将n个元素分成各含n/2个元素的子序列，然后对两个子序列递归地进行排序，最后合并两个已排序的子序列得到排序结果。二分查找的思想是对于集合中的每一个数字，用二分法找到x-S[i]的位置，若存在且不为其本身，则输出S中存在有两个和等于x的元素；否则，不存在

3、。(4)实验结果222.实现优先队列(1)问题描述实现优先队列，维护一组元素构成的集合S。(2)问题分析优先队列是基于堆排序的。首先将集合S中的元素进行堆排序。当进行操作时，要不断维护集合S的有序性，即要不断地调整堆。(3)算法分析本程序中主要的函数有INSERT()：需要调用INCREASE_KEY()来维护堆，其时间复杂度为O（lgn），函数MAXIMUM()仅需要返回S[1]，时间复杂度为(1)，函数EXTRACT_MAX()需要调用堆排序中的MAX_HEAPIFY，时间复杂度为O(lgn)，函数INCREASE_KE

4、Y()更新结点到根结点的路径长度为O(lgn)，时间复杂度为O(lgn)。3.快速排序(1)问题描述实现快速排序(2)问题分析快速排序采用了分治策略。数组A[p..r]被划分成两个子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A(q)，而且，小于等于A[q+1..r]中的元素。然后通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序。最后将两个数组合并。(3)算法分析22快速排序不需要额外的辅助空间，其时间复杂度在平均情况下为O(nlgn)，最坏情况下为O()。

5、快速排序是不稳定的排序算法。(1)实验结果4.第k大元素(1)问题描述给定两个大小分别为m和n的有序序列，采用分治法求解两个序列合起来的第k大元素，使得时间复杂度为O(lgm+lgn)。(2)问题分析将A平均分为前后两个部分，前半部分有x个元素，后半部分有m-x个元素。因为A有序，所以后半部分的所有元素均大于前半部分。A[x]为后半部分的第一个元素。将B也平均分为前后两个部分，前半部分有y个元素，后半部分有n-y个元素。B[y]是后半部分的第一个元素。(3)算法分析由于两个数组都是平均划分的，我们可以近似地认为x=m/2,y

6、=n/2。假设A[x]<=B[y],则有a.22B[y]前面至少有x+y个元素，如果k<=x+y，合并后第k大元素必然在B[y]前面，所以原来B数组中的后半部分可以排除掉。b.合并后A[x]后面至少有(n+m)-(x+y)个元素，如果k>x+y，合并后第k大元素必然在A[x]后面。所以，原来在A数组中前半部分可以排除掉。实验二动态规划1.矩阵链乘(1)题目要求给定n个矩阵链，矩阵Ai的规模为pi-1*pi（1≤i≤n），求完全括号化方案，使得A1A2,...An所需标量乘法次数最小。(2)题目分析

7、本问题满足最优子结构性质（矩阵链乘AiAi+1...Aj的最优化括号方案包含其子问题AiAi+1...Ak和Ak+1Ai+1...Aj的最优括号方案）：假设AiAi+1,...Aj所的最优括号化方案的分割点在Ak和Ak+1之间。那么，继续对前缀子链AiAi+1,...Ak优化我们应该采用独立求解它时所得的最优化方案。同理，在子链Ak+1Ak+2,...Aj进行括号化的方法，就是它自身的最优化括号方案。所以可以用动态规划来求解。(3)算法分析为了构造一个矩阵链乘问题的最优解，我们可以将问题划分为两个子问题（AiAi+1...A

8、k和Ak+1Ai+1...Aj的最优括号化问题），求出子问题的解，然后将子问题的最优解组合起来，同时必须保证考察了所以的可能的分割点。22设m[i,j]表示计算AiAi+1...Aj所需标量乘法次数的最小值，则原问题的最优解就是m[1,n]。AiAi+1...Aj的最小代价括号方案的递归求