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