Prim算法与穷举算法的时间复杂度分析

1、 格式支持编辑，如有帮助欢迎下载支持。 PAGE PAGE 4如有帮助欢迎下载支持Prim 算法与穷举算法的时间复杂度分析1、基本概念生成树。最小生成树的性质：N=(V,E) V (u,v)权值的边，其中u 属于U，v 属于V(u,v)的最小生成树。Prim 的时间复杂度。2、两种算法的思想Prim算法思想：首先将初始顶点u U 中，对其余每一个顶点iclosedgei初始化为到点u 息。循环n-1次1）从各组最小边closedgev中选出最小的最小边closedgek0(v,k0 属于V-U);k加入到U 中;更新剩余的每组最小边信息closedgev(vV-U).对于以 v 为中心的那组边

2、，新增加了一条从 k0 到 v 的边，如果新边的权值比closedgev.lowcost 小，则将closedgev.lowcost 更新为新边的权值.穷举算法思想：首先将初始顶点u 加入到U 中，其余顶点加入到V 中，h 赋值为无穷大穷举下列步骤从U 中选择一个顶点a，从V 中选择另外一个顶点b如果两个顶点间的距离不为无穷大，则将b 加入到U 中，从V 中移除ba-b的权值如果V不为空，转到，如果V 为空，而且权值比h小，将权值赋值给h时间复杂度分析Prim时间复杂度分析n 次n 次2 1)n 次2 2)1 次2 3)n 次T(n)=n+n*(n+1+n)=n+2n2+n=2O(n2)穷举复

3、杂度分析n 次2 (n-1)*1+(n-2)*2+1*(n-1) 次1) n 次2 2) n 次2 3) n 次T(n)=n+(n-1)*1+(n-2)*2+1*(n-1)*(n+n+n)=n+(n*n+n*n+n*n)*3n=n+3n3=3O(n3)矩阵连乘动态规划算法1、问题描述nA,A,AAA 是可乘的n12nii+1阵的连乘积AAA1 2n算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，2矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A 是完全加括号的，则A2BCA=(BC)。ABCD有5种不同的完全加括号的方式

4、A30*5，则五种算法需要的计算次数分别为16000,10500,36000,87500,35000是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继nA1,A2,An（其中矩阵Ai 的维数为Pi-1 * Pi，i1,2,n），A1,A2,An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 乘积的最优计算次序问题。二、算法思路所有已解决的子问题的答案，不管该子问题以后是否被用到， 只要它被计算过，就将其结果填入表中。本实验的算法思路是：0次矩阵的列数矩阵连乘次数最少的算法，其中一部分的运算也是最少的（或者叫最优的由以上可以推出矩阵连乘最少算法的递归公式：M

5、in = Mik + Mi+1 n +P(i-1)*P(k)*P(j)使用递归公式，可以很快地找到最少计算次数的计算方法主要的递归函数：int calcu(int i,int j,int p,char st) int nmin=47;if(i=j)char m250;gcvt(i,10,m);/ 拼 接 a 和 i strcat(st,a);strcat(st,m); return 0;elsefor(int k=i;kj;k+) char st1250=0;char st2250=0;int mp=calcu(i,k,p,st1)+calcu(k+1,j,p,st2)+pi-1*pk*pj; if (mpnmin)nmin=mp;st0=0;strcat