算法导论上机报告

算法导论上机报告班级: 1313012学号:姓名: 黄帮振描述一个运行时间为θ(nlgn)的算法给定n个整数的集合S与另一个整数x该算法能确定S中就是否存在两个其与刚好为x的元素。

一、算法分析1、运用归并排序算法归并排序运用的就是分治思想,时间复杂度为θ(nlgn)能够满足题目要求的运行时间。

归并排序的分解部分就是每次将数组划分两个部分,时间复杂度为θ(1)再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止。

解决部分就是递归求解排序子序列,合并部分就是将已经排序的子序列进行合并得到所要的答案,时间复杂度为θ(lgn)。

2、在已经排好序的基础上,对其运用二分查找二分查找算法的时间复杂度为θ(lgn)在题目要求的范围内,二分查找的条件为待查的数组为有序序列。

算法的主要思想为设定两个数low指向最低元素high指向最高元素,然后比较数组中间的元素与待查元素进行比较。

如果待查元素小于中间元素,那么表明查找元素在数组的前半段,反之,如果待查元素大于中间元素,那么表明查找元素在实现优先队列排序算法,需要支持以下操作:INSERT(S,x):把元素x插入到集合S中MAXMUM(S):返回S中具有最大key的元素EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素INCREASE-KEY(S,x,k):将元素x的关键字值增到k。

一、算法原理快速排序采用分治策略,时间复杂度为θ(nlgn),但就是最坏情况下为θ(n2),并且快速排序算法属于原地排序,并不需要开辟空间。

快速排序复杂的步骤为其分解的步骤分解的过程数组A[p、、r]被划分为两个子数组A[p、、q-1]与A[q+1、、r],使得A[p、、q-1]中的每个元素都小于A[q],而A[q]也小于等于A[q+1、、r]中的每个元素。

而在实现的过程总就是选择将A[r]作为基准点进行划分A[p、、r]数组。

二、伪代码QUICKSORT(A,p,r)1 if p < r2 q = PARTITION(A,p,q)3 QUICKSORT(A,p,q-1)4 QUICKSORT(A,q+1,r)PARTITION(A,p,r)1 x = A[r]2 i = p-13 for j = p to r-14 if A[j] x5 i = i+16 exchange A[i] with A[j]7 exchange A[i+1] with A[r]8 return i + 1三、实验总结问题答案:当选取第一个或者最后一个为基准点时,当n个元素相同的时候为最坏情况比较次数为n*(n-1)/2;快速排序比较次数最少为θ(nlgn),,最大的比较次数为θ(n2)。

运用分治的策略将两个已经排好序的序列中,找出第k大的元素且要求时间复杂度为θ(lgm+lgn),其中m与n分别为两个序列的长度。

一、算法原理1最优子结构为:如果最优的加括号的方式将其分解为Ai、、k与Ak+1、、j的乘积则分别对Ai、、k与Ak+1、、j加括号的方式也一定就是最优的。

2定义m[i,j]为计算矩阵Ai、、j所需标量乘法次数的最小值,对于i=j时,矩阵链乘只包含唯一的矩阵Ai,因此不需要做任何标量乘法运算,所以m[i,i]=0;当i<j时利用最优子结构来计算m[i,j]。

3矩阵链乘的递归式4在算法设计的时候需要m数组记录Ai、、j最小相乘次数,s数组记录构造最优解所需要的信息,其记录的k值指出了AiAi+1Aj的最优括号化方案的分割点应在AkAk+1之间。

5 矩阵链乘的时间复杂度为θ(n3)二、伪代码MATRIX-CHAIN-ORDER(p)1、n=p、length-12、Let m[1、、n,1、、n] and s[1、、n-1,2、、n] be new tables3、For i=1 to n4、 M[i,i]=05、for l=2 to n6、 For i=1 to n-l+17、 J=i+l-18、 M[i,j]=无穷9、 For k=i to j-110、 Q=m[i,k]+m[k+1,j]+p(i-1)*p(k)*p(j)11、 If q<m[i,j]12、 M[i,j]=q13、 S[i,j]=k一、算法原理1最优子结构:令X=<x1,x2,、、xm>与Y=<y1,y2,、、、,yn>为两个序列Z=<z1,z2,、、、,zk>为X与Y的任意LCS。

如果xm=yn,则zk=xm=yn且Zk-1就是Xm-1与Yn-1的一个LCS;如果xm≠yn,则zk≠xm意味着Z就是Xm-1与Y的一个LCS;如果xm ≠yn,则zk≠yn意味着Z就是X与Yn-1的一个LCS。

2定义一个b[i,j]指向表项对应计算c[i,j]时所选择的子问题最优解,过程返回表b与表c,c[m,n]保持X与Y的LCS长度。

3LCS的递归式为4LCS的时间复杂度为θ(m+n),b表的空间复杂度为θ(mn)。

二、伪代码LCS-LENGTH(X,Y)1.m=X、length2.n=Y、length3.Let b[1、、m,1、、n] and c[0、、m,0、、n] be new tables4.For i=1 to m5. c[i,0]=06.For j=0 to n7. c[0,j]=08.For i=1 to m9. For j=1 to n一、算法原理1最优子结构令X=<x1,x2,、、xm>与Y=<y1,y2,、、、,yn>为两个序列Z=<z1,z2,、、、,zk>为X与Y的任意最长公共子串。

如果xm=yn,则zk=xm=yn且Zk-1就是Xm-1与Yn-1的一个最长公共子串; 如果xm≠yn,则zk≠xm意味着Z就是Xm-1与Y的一个最长公共子串;如果xm≠yn,则zk≠yn意味着Z就是X与Yn-1的一个最长公共子串。

2定义L[i,j]为以x[i]与y[j]为结尾的相同子串的最大长度,记录着X与Y的最长公共子串的最大长度。

3最长公共子串的递归式4最长公共子串的时间复杂度为θ(mn),空间复杂度为θ(mn)。

二、伪代码getLCString(str1,tr2)len1 = str1、length;len2 = str2、length;maxLen = len1 > len2 ? len1 : len2;for j to maxLenif max[j] > 0Print j + 1for i = maxIndex[j] - max[j] + 1 to maxIndex[j]Print str1[i]三、实验总结要同上述的最长公共子序列进行对比区分她们的不同之处。

也要理解用动态规划求解时的相同之处与不同之处。

一、算法原理1 最优子结构:定义当所给整数全为负数的时候,最大子段与为0,则最大子段与为max{0,a[i]+a[i+1]、、、+a[j]},1≤i≤j≤n2 引入一个辅助数组b,动态规划的分解分为两步:(1)计算辅助数组的值;(2)计算辅助数组的最大值。

辅助数组b[j]用来记录以j为尾的子段以及集合中的最大子段与。

3 最大子段与的递归式一、算法原理1可以由图可知,图中的顶点讲图划分7个阶段,分别了解每个阶段可以有几种可供选择的点,引入f[k]表示状态k到终点状态的最短距离。

最优子结构为当前状态的f[k]由上个状态的f[k-1]与状态k-1到状态k的距离决定决策:当前状态应在前一个状态的基础上获得。

决策需要满足规划方程,规划方程f(k)表示状态k到终点状态的最短距离。

2多段图最短路径的递归式二、伪代码Shortestpathlet indexs [0、、W1[0]、length],isLabel [0、、W1[0]、length] be a new table i_count = -1distance = W1[start]index = startpresentShortest = 0indexs[++i_count] = index;isLabel[index] = true;while i_count<W1[0]、lengthmin = Integer、MAX_VALUE;for i = 0 to distance、lengthif !isLabel[i] and distance[i] != -1 and i != indexif distance[i] < minmin = distance[i]index = iif index == end一、算法原理10-1背包问题:选择n个元素中的若干个来形成最优解,假定为k个。

对于这k个元素a1, a2, 、、、ak来说,它们组成的物品组合必然满足总重量<=背包重量限制,而且它们的价值必然就是最大的。

假定ak就是我们按照前面顺序放入的最后一个物品,它的重量为wk,它的价值为vk。

前面k个元素构成了最优选择,把ak物品拿走,对应于k-1个物品来说,它们所涵盖的重量范围为0-(W-wk)。

假定W为背包允许承重的量,最终的价值就是V,剩下的物品所构成的价值为V-vk。

这剩下的k-1个元素构成了W-wk的最优解。

2分数背包问题:所选择的的贪心策略为按照选择单位重量价值最大的物品顺序进行挑选。

算法的步骤:设背包容量为C共有n个物品物品重量存放在数组W[n]中价值存放在数组V[n]中问题的解存放在数组X[n]中。

第一步,改变数组W与V的排列顺序使其按单位重量价值V[i]/W[i]降序排列,并将数组X[n]初始化为0;第二步初始化i=0,设计一个循环,循环终止条件为W[i]>C,循环体为将第i个物品放入背包,X[i]=1;C=C-W[i];i++最后一步将结果存入到X数组中X[i]=C/W[i]。

3 分数背包问题采用选择单位重量价值最大的物品顺序进行挑选,其算法的时间复杂度为θ(nlgn)。

4 背包问题的递归式:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}二、伪代码Knapsack01(v,w,weight)1.n=w、length2.let c[0、、n,0、、weight] be a new table3.For i=0 to n4. c[i,0]=05.For j=1 to weight6. c[0,j]=0Bellman-Ford算法通过对边进行松弛操作来渐近地降低从源点A到每个结点的最短路径的估计值,直到该估计值与实际的最短路径权重相同为止。

该算法返回TRUE值当且仅当输入图中不包含可以从源结点到达的权重为负值的环路。

Bellman-Ford算法的执行步骤:1、初始化:将除源点外的所有顶点的最短距离估计值d[v]←+∞, d[s]←0;2、迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离,运行|v|-1次;3、检验负权回路,判断边集E中的每一条边的两个端点就是否收敛。