资源描述：
《Prim算法与穷举算法的时间复杂度分析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途Ｐrim算法与穷举算法的时间复杂度分析1、基本概念在一个连通网的所有生成树中,各边的代价之和最小的那棵生成树称为该连通网的最小生成树。ﻩ最小生成树的性质:设N=(V,{Ｅ｝)是一个连通网,Ｕ是顶点集V的一个非空子集,若(u,ｖ)是一条具有最小权值的边,其中ｕ属于U,v属于V,则存在一颗包含边(u,ｖ)的最小生成树。ﻩＰｒim算法就是利用这一性质来求最小生成树的,与穷举算法相比,Prim算法拥有更好的时间复杂度。2、两种算法的思想A.Pｒiｍ算法思想：１首先将初始顶点ｕ加入到U中，对其余每一个顶点i,将closedge[ｉ］初
2、始化为到点u的信息。2循环n-１次1)从各组最小边cloｓeｄｇe［ｖ]中选出最小的最小边cloｓedgｅ[k0](ｖ,ｋ0属于V-Ｕ);2) 将ｋ加入到U中;3)更新剩余的每组最小边信息closedｇe[v](v属于V-Ｕ).对于以v为中心的那组边,新增加了一条从k0到ｖ的边,如果新边的权值比cｌｏseｄge［ｖ].lｏｗcｏst小,则将cｌosｅｄgｅ[ｖ］.ｌowcoｓt更新为新边的权值.B.穷举算法思想:1首先将初始顶点u加入到Ｕ中，其余顶点加入到Ｖ中,ｈ赋值为无穷大２穷举下列步骤1)从U中选择一个顶点a，从V中选择另外一个顶点ｂ２)如果两
3、个顶点间的距离不为无穷大,则将b加入到Ｕ中，从Ｖ中移除b，当前权值加上ａ-b的权值3)如果V不为空,转到1）,如果Ｖ为空，而且权值比ｈ小，将权值赋值给h3.时间复杂度分析A．Prｉｍ时间复杂度分析1n次２n次２1)n次22)1次23）n次个人收集整理勿做商业用途Ｔ（n)＝n+ｎ＊(n＋１＋n)=n+２n^2+n=2O（ｎ^2)B.穷举复杂度分析１ ｎ次2(n-１)*1+（n-２)＊2+…+1＊(n－1) 次2 1) n次2２） n次２3)ｎ次T(n)=n＋(（n-1)*1+(n－2)*2+…+1＊(n-1))*（n+ｎ+n）<＝n+(n*n+ｎ＊n
4、+…+n＊n)＊3n =n+3n^３ =３O（n^３)个人收集整理勿做商业用途矩阵连乘动态规划算法1、问题描述给定ｎ个矩阵｛A1，A2,…,An},其中Ai与Ａi+1是可乘的,i＝1,2，…,n-1。要算出这ｎ个矩阵的连乘积Ａ1A２…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用２个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵
5、连乘积A是完全加括号的，则A可表示为２个完全加括号的矩阵连乘积B和Ｃ的乘积并加括号,即Ａ=(BC)。例如，矩阵连乘积ＡBCD有5种不同的完全加括号的方式:A((BＣ)D),A（Ｂ(ＣD)),（ＡB)(CB)，((ＡB)C)D，(A(BＣ)）Ｄ。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A为50*１0,B为10*40,C为40*３0，D为30*5,则五种算法需要的计算次数分别为1６００0,10５０0,360０0,875０0,35000次。由此可见，在计算矩阵连乘积时,加括号方式，即计算次序对计算量有很大的影
6、响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵｛A１，A２,…,An｝(其中矩阵Ａｉ的维数为Ｐｉ-1 ＊Ｐi,i=1,2,…，n）,如何确定计算矩阵连乘积{A1,A2,…，An}的计算次序(完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。二、算法思路动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是,动态规划法经分解得到的子问题往往不是相互
7、独立的,前一子问题的解为后一子问题的解提供有用的信息,可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。本实验的算法思路是:1一个矩阵,运算0次2两组矩阵，运算次数为两组矩阵自身的运算次数之和再加上第一个矩阵的行数*最后一个矩阵的列数3矩阵连乘次数最少的算法,其中一部分的运算也是最少的（或者叫最优的）由以上可以推出矩阵连乘最少算法的递归公式:Mｉn=Mik ＋Ｍi+1 n+ P(i-1)*P(k）*P(j)使用递归公式，可以很快地找到最少计算次数的计算方法主要的递归函数:int ｃalcu（
8、ｉnti,int j,iｎtp[],chａrst[]){ｉntnmin=2147４8３647;个人收集整理勿做商业用途ﻩｉ
