1、*Prim 算法與窮舉算法的時間復(fù)雜度分析1、基本概念在一個連通網(wǎng)的所有生成樹中， 各邊的代價之和最小的那棵生成樹稱為該連通網(wǎng)的最小生成樹。最小生成樹的性質(zhì)：設(shè) N=(V,E) 是一個連通網(wǎng)， U 是頂點集 V 的一個非空子集，若 (u,v) 是一條具有最小權(quán)值的邊，其中 u 屬于 U， v 屬于 V ，則存在一顆包含邊 (u,v) 的最小生成樹。Prim 算法就是利用這一性質(zhì)來求最小生成樹的，與窮舉算法相比，Prim 算法擁有更好的時間復(fù)雜度。2、兩種算法的思想A.Prim算法思想：1 首先將初始頂點 u 加入到 U 中，對其余每一個頂點 i ，將 closedgei 初始化為到點 u 的信

2、息。2 循環(huán) n-1 次1）從各組最小邊closedgev 中選出最小的最小邊closedgek0(v,k0 屬于 V-U);2)將 k 加入到 U 中 ;3)更新剩余的每組最小邊信息closedgev(v 屬于 V-U).對于以 v 為中心的那組邊，新增加了一條從k0到 v 的邊，如果新邊的權(quán)值比closedgev.lowcost 小，則將closedgev.lowcost 更新為新邊的權(quán)值.B.窮舉算法思想：1 首先將初始頂點u 加入到 U 中，其余頂點加入到V 中， h 賦值為無窮大2 窮舉下列步驟1)從 U 中選擇一個頂點a，從 V 中選擇另外一個頂點b2)如果兩個頂點間的距離不為無窮

3、大，則將b 加入到 U 中，從 V 中移除 b，當(dāng)前權(quán)值加上 a-b 的權(quán)值3)如果 V 不為空，轉(zhuǎn)到1），如果 V 為空，而且權(quán)值比h 小，將權(quán)值賦值給 h3. 時間復(fù)雜度分析A.Prim時間復(fù)雜度分析1 n 次2 n 次2 1)n 次22)1次2 3)n 次T(n)=n+n*(n+1+n)1*=n+2n2+n=2O(n2)B.窮舉復(fù)雜度分析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+3n3=3O(n3)2*

4、矩陣連乘動態(tài)規(guī)劃算法1、問題描述給定 n 個矩陣 A1,A 2,A n ，其中 Ai 與 Ai+1 是可乘的， i=1,2,n-1 。要算出這n 個矩陣的連乘積A1A2 An。由于矩陣乘法滿足結(jié)合律，故計算矩陣的連乘積可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2 個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積。完全加括號的矩陣連乘積可遞歸地定義為：（ 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 。每一種完全加括號的方式對應(yīng)于一個矩陣連乘積的計算次序，這決定著作乘積所需要的計算量。若 A 為 50*10 ，B 為 10*40 ， C為 40*30 ，D 為 30*5 ，則五種算法需要的計算次數(shù)分別為16000,10500,36000,87500,35000次。由此可見， 在計算矩陣連乘積時，加括號方式，即計算次序?qū)τ嬎懔坑泻艽蟮挠绊?。于是，自然提出矩陣連乘積的最優(yōu)計算次序問題，即對于給定的相繼n 個矩陣 A,A, ,A12n（其中矩陣 A

6、的維數(shù)為 P* P ， i 1,2, ,n ），如何確定計算矩陣連乘積A ,A2, ,Aii-1i1n的計算次序（完全加括號方式），使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。窮舉搜索法的計算量太大，它不是一個有效的算法， 本實驗采用動態(tài)規(guī)劃算法解矩陣連乘積的最優(yōu)計算次序問題。二、算法思路動態(tài)規(guī)劃算法的基本思想是將待求解問題分成若干個子問題，先求解子問題， 然后從這些子問題的解得到原問題的解。與分治法不同的是，動態(tài)規(guī)劃法經(jīng)分解得到的子問題往往不是相互獨立的， 前一子問題的解為后一子問題的解提供有用的信息，可以用一個表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計算過，

7、就將其結(jié)果填入表中。本實驗的算法思路是：1 一個矩陣，運算0 次2 兩組矩陣，運算次數(shù)為兩組矩陣自身的運算次數(shù)之和再加上第一個矩陣的行數(shù)*最后一個矩陣的列數(shù)3 矩陣連乘次數(shù)最少的算法，其中一部分的運算也是最少的（或者叫最優(yōu)的）由以上可以推出矩陣連乘最少算法的遞歸公式：M in = M ik + M i+1 n + P(i-1)*P(k)*P(j)使用遞歸公式，可以很快地找到最少計算次數(shù)的計算方法主要的遞歸函數(shù)：int calcu(int i,int j,int p,char st)int nmin=2147483647;if(i=j)char m250;3*gcvt(i,10,m);/拼接 a和 istrcat(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)