資源描述：
《Prim算法與窮舉算法的時(shí)間復(fù)雜度分析.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、個(gè)人收集整理勿做商業(yè)用途Ｐrim算法與窮舉算法的時(shí)間復(fù)雜度分析1、基本概念在一個(gè)連通網(wǎng)的所有生成樹中,各邊的代價(jià)之和最小的那棵生成樹稱為該連通網(wǎng)的最小生成樹。?最小生成樹的性質(zhì):設(shè)N=(V,{Ｅ｝)是一個(gè)連通網(wǎng),Ｕ是頂點(diǎn)集V的一個(gè)非空子集,若(u,ｖ)是一條具有最小權(quán)值的邊,其中ｕ屬于U,v屬于V,則存在一顆包含邊(u,ｖ)的最小生成樹。?Ｐｒim算法就是利用這一性質(zhì)來求最小生成樹的,與窮舉算法相比,Prim算法擁有更好的時(shí)間復(fù)雜度。2、兩種算法的思想A.Pｒiｍ算法思想：１首先將初始頂點(diǎn)ｕ加入到U中，對其余每一個(gè)頂點(diǎn)i,將closedge[ｉ］初
2、始化為到點(diǎn)u的信息。2循環(huán)n-１次1)從各組最小邊cloｓeｄｇe［ｖ]中選出最小的最小邊cloｓedgｅ[k0](ｖ,ｋ0屬于V-Ｕ);2) 將ｋ加入到U中;3)更新剩余的每組最小邊信息closedｇe[v](v屬于V-Ｕ).對于以v為中心的那組邊,新增加了一條從k0到ｖ的邊,如果新邊的權(quán)值比cｌｏseｄge［ｖ].lｏｗcｏst小,則將cｌosｅｄgｅ[ｖ］.ｌowcoｓt更新為新邊的權(quán)值.B.窮舉算法思想:1首先將初始頂點(diǎn)u加入到Ｕ中，其余頂點(diǎn)加入到Ｖ中,ｈ賦值為無窮大２窮舉下列步驟1)從U中選擇一個(gè)頂點(diǎn)a，從V中選擇另外一個(gè)頂點(diǎn)ｂ２)如果兩
3、個(gè)頂點(diǎn)間的距離不為無窮大,則將b加入到Ｕ中，從Ｖ中移除b，當(dāng)前權(quán)值加上ａ-b的權(quán)值3)如果V不為空,轉(zhuǎn)到1）,如果Ｖ為空，而且權(quán)值比ｈ小，將權(quán)值賦值給h3.時(shí)間復(fù)雜度分析A．Prｉｍ時(shí)間復(fù)雜度分析1n次２n次２1)n次22)1次23）n次個(gè)人收集整理勿做商業(yè)用途Ｔ（n)＝n+ｎ＊(n＋１＋n)=n+２n^2+n=2O（ｎ^2)B.窮舉復(fù)雜度分析１ ｎ次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^３)個(gè)人收集整理勿做商業(yè)用途矩陣連乘動(dòng)態(tài)規(guī)劃算法1、問題描述給定ｎ個(gè)矩陣｛A1，A2,…,An},其中Ai與Ａi+1是可乘的,i＝1,2，…,n-1。要算出這ｎ個(gè)矩陣的連乘積Ａ1A２…An。由于矩陣乘法滿足結(jié)合律，故計(jì)算矩陣的連乘積可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用２個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。完全加括號的矩陣連乘積可遞歸地定義為：（1）單個(gè)矩陣是完全加括號的；（2）矩陣
5、連乘積A是完全加括號的，則A可表示為２個(gè)完全加括號的矩陣連乘積B和Ｃ的乘積并加括號,即Ａ=(BC)。例如，矩陣連乘積ＡBCD有5種不同的完全加括號的方式:A((BＣ)D),A（Ｂ(ＣD)),（ＡB)(CB)，((ＡB)C)D，(A(BＣ)）Ｄ。每一種完全加括號的方式對應(yīng)于一個(gè)矩陣連乘積的計(jì)算次序，這決定著作乘積所需要的計(jì)算量。若A為50*１0,B為10*40,C為40*３0，D為30*5,則五種算法需要的計(jì)算次數(shù)分別為1６００0,10５０0,360０0,875０0,35000次。由此可見，在計(jì)算矩陣連乘積時(shí),加括號方式，即計(jì)算次序?qū)τ?jì)算量有很大的影
6、響。于是，自然提出矩陣連乘積的最優(yōu)計(jì)算次序問題，即對于給定的相繼n個(gè)矩陣｛A１，A２,…,An｝(其中矩陣Ａｉ的維數(shù)為Ｐｉ-1 ＊Ｐi,i=1,2,…，n）,如何確定計(jì)算矩陣連乘積{A1,A2,…，An}的計(jì)算次序(完全加括號方式），使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。窮舉搜索法的計(jì)算量太大，它不是一個(gè)有效的算法，本實(shí)驗(yàn)采用動(dòng)態(tài)規(guī)劃算法解矩陣連乘積的最優(yōu)計(jì)算次序問題。二、算法思路動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是,動(dòng)態(tài)規(guī)劃法經(jīng)分解得到的子問題往往不是相互
7、獨(dú)立的,前一子問題的解為后一子問題的解提供有用的信息,可以用一個(gè)表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。本實(shí)驗(yàn)的算法思路是:1一個(gè)矩陣,運(yùn)算0次2兩組矩陣，運(yùn)算次數(shù)為兩組矩陣自身的運(yùn)算次數(shù)之和再加上第一個(gè)矩陣的行數(shù)*最后一個(gè)矩陣的列數(shù)3矩陣連乘次數(shù)最少的算法,其中一部分的運(yùn)算也是最少的（或者叫最優(yōu)的）由以上可以推出矩陣連乘最少算法的遞歸公式:Mｉn=Mik ＋Ｍi+1 n+ P(i-1)*P(k）*P(j)使用遞歸公式，可以很快地找到最少計(jì)算次數(shù)的計(jì)算方法主要的遞歸函數(shù):int?。鉧lcu（
8、ｉnti,int j,iｎtp[],chａrst[]){ｉntnmin=2147４8３647;個(gè)人收集整理勿做商業(yè)用途?ｉ
