Prim算法与穷举算法的时间复杂度分析下载_Word模板_8

Prim算法与穷举算法的时间复杂度分析 1、基本概念在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小生成树。最小生成树的性质：设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值的边，其中u属于U，v属于V，则存在一颗包含边(u,v)的最小生成树。Prim算法就是利用这一性质来求最小生成树的，与穷举算法相比，Prim算法拥有更好的时间复杂度。2、两种算法的思想A.Prim算法思想：1首先将初始顶点u加入到U中，对其余每一个顶点i，将closedge[i]初始化为到点u的信息。2循环n-1次1）从各组最小边closedge[v]中选出最小的最小边closedge[k0](v,k0属于V-U);2)将k加入到U中;3)更新剩余的每组最小边信息closedge[v](v属于V-U).对于以v为中心的那组边，新增加了一条从k0到v的边，如果新边的权值比closedge[v].lowcost小，则将closedge[v].lowcost更新为新边的权值.B.穷举算法思想：1首先将初始顶点u加入到U中，其余顶点加入到V中，h赋值为无穷大2穷举下列步骤1)从U中选择一个顶点a，从V中选择另外一个顶点b2)如果两个顶点间的距离不为无穷大，则将b加入到U中，从V中移除b，当前权值加上a-b的权值3)如果V不为空，转到1），如果V为空，而且权值比h小，将权值赋值给h3.时间复杂度分析A.Prim时间复杂度分析1n次2n次21)n次22)1次23)n次T(n)=nn*(n1n)=n2n^2n=2O(n^2)B.穷举复杂度分析1n次2(n-1)*1(n-2)*2…1*(n-1)次21)n次22)n次23)n次T(n)=n((n-1)*1(n-2)*2…1*(n-1))*(nnn)<=n(n*nn*n…n*n)*3n=n3n^3=3O(n^3)矩阵连乘动态规划算法1、问题描述给定n个矩阵{A1,A2,…,An}，其中Ai与Ai1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积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个矩阵{A1,A2,…,An}（其中矩阵Ai的维数为Pi-1*Pi，i＝1,2,…,n），如何确定计算矩阵连乘积{A1,A2,…,An}的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。二、算法思路动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。本实验的算法思路是：1一个矩阵，运算0次2两组矩阵，运算次数为两组矩阵自身的运算次数之和再加上第一个矩阵的行数*最后一个矩阵的列数3矩阵连乘次数最少的算法，其中一部分的运算也是最少的（或者叫最优的）由以上可以推出矩阵连乘最少算法的递归公式：Min=MikMi1nP(i-1)*P(k)*P(j)使用递归公式，可以很快地找到最少计算次数的计算方法主要的递归函数：intcalcu(inti,intj,intp[],charst[]){intnmin=2147483647;if(i==j){charm[250];gcvt(i,10,m);//拼接"a"和istrcat(st,"a");strcat(st,m);return0;}else{for(intk=i;k

                    本文档为【Prim算法与穷举算法的时间复杂度分析】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

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

你可能还喜欢