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

1、Prim 算法与穷举算法的时间复杂度分析1、基本概念在一个连通网的所有生成树中， 各边的代价之和最小的那棵生成树称为该连通网的最小 生成树。最小生成树的性质：设 N=(V,E) 是一个连通网， U 是顶点集 V 的一个非空子集，若 (u,v) 是一条具有最小 权值的边，其中u属于U , v属于V，则存在一颗包含边(u,v)的最小生成树。Prim 算法就是利用这一性质来求最小生成树的，与穷举算法相比， Prim 算法拥有更好 的时间复杂度。2、两种算法的思想A.Prim 算法思想：1首先将初始顶点 u加入到U中，对其余每一个顶点i，将closedgei初始化为到点u的信 息。2 循环 n-1 次

2、1) 从各组最小边 closedgev 中选出最小的最小边 closedgek0(v,k0 属于 V-U);2) 将 k 加入到 U 中 ;3) 更新剩余的每组最小边信息 closedgev(v 属于 V-U).对于以 v 为中心的那组边，新增加了一条从 k0 到 v 的边，如果新边的权值比closedgev.lowcost 小，则将 closedgev.lowcost 更新为新边的权值 .B.穷举算法思想：1首先将初始顶点 u加入到U中，其余顶点加入到 V中，h赋值为无穷大2 穷举下列步骤1) 从U中选择一个顶点a,从V中选择另外一个顶点 b2) 如果两个顶点间的距离不为无穷大，则将b加入到

3、U中，从V中移除b，当前权值加上 a-b 的权值3) 如果 V 不为空，转到 1 )，如果 V 为空，而且权值比 h 小，将权值赋值给 h3. 时间复杂度分析A.Prim 时间复杂度分析1 n 次2 n次2 1)n 次2 2)1 次2 3)n 次T(n)=n+n*(n+1+n)=n+2nA2+n=20(门人2)B.穷举复杂度分析1 n 次2 (n-1)*1+( n-2)*2+ +1*( n-1) 次2 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+3nA

4、3=30(nA3)矩阵连乘动态规划算法1、问题描述给定n个矩阵Ai,A2,A n，其中A与A+1是可乘的，i=1,2,n -1。要算出这n个矩 阵的连乘积 AA2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计 算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定， 也就是说该连乘积已完全加括号， 则可以依此次序反复调用 2 个矩阵相乘的标准算法计算出 矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：(1)单个矩阵是完全加括号的；(2)矩阵连乘积 A是完全加括号的，则 A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即 A=(BC)。

5、例如，矩阵连乘积ABCD有 5种不同的完全加括号的方式：A(BC)D) ,A(B(CD) , (AB)(CB)， (AB)C)D ，(A(BC)D 。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A为50*10，B为10*40, C为40*30, D为30*5，则五种算法需要的计算次数分别为 16000,10500,36000,87500,35000 次。由此可见, 在计算矩阵连乘积时,加括号方式,即计算次序对计算量有很大的影响。于 是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵Ai,A2,An(其中矩阵A的维数为P-1 * Pi ,

6、 i = 1,2,n )，如何确定计算矩阵连乘积Ai,A2,An的计算次序(完全加括号方式),使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举搜索法的计算量太大, 它不是一个有效的算法, 本实验采用动态规划算法解矩阵连 乘积的最优计算次序问题。二、算法思路动态规划算法的基本思想是将待求解问题分成若干个子问题,先求解子问题, 然后从这些子问题的解得到原问题的解。与分治法不同的是,动态规划法经分解得到的子问题往往不是相互独立的, 前一子问题的解为后一子问题的解提供有用的信息, 可以用一个表来记录 所有已解决的子问题的答案,不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。本实验的算

7、法思路是：1 一个矩阵,运算 0次2 两组矩阵,运算次数为两组矩阵自身的运算次数之和再加上第一个矩阵的行数*最后一个矩阵的列数3 矩阵连乘次数最少的算法,其中一部分的运算也是最少的(或者叫最优的) 由以上可以推出矩阵连乘最少算法的递归公式：Min = 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"和istrcat(st,"a");strcat(st,m);return 0;elsefor(i nt k=i;k<j;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 (mp <nmin)n mi n=mp;拼接 ”(”,st1,"*",st2,")"stO=&#