算法分析與設(shè)計復(fù)習(xí)大綱

算法分析與設(shè)計復(fù)習(xí)大綱第1章緒論考點.P八\、?1、算法的5個重要特性。答：輸入、輸出、有窮性、確定性、可行性2、掌握擴展遞歸技術(shù)和通用分治遞推式的使用。擴展遞歸技術(shù)：T(n)=7T(n)=72T(n/2)+5n2n=vz?>1r(//)=2T(n/2)=2(2T(?/4)4-5(/f/2)2)+為亍=2(2(2T(n/8)+5(n/l)2)+5(m/z/)+5n2=2Ar(l)+2^-15^^)2+…+2X5(S+5n2地）二地）二7"5斗日=10/;2-3?〈10/二0(/)通用分支遞歸式:r（/zr（/z）aT(〃/Z>)+cnk71>1。(我3)?>bk7"(?z)=VO(Z?Alogz,M)?=bkO(n*)abk5、使用擴展遞歸技術(shù)求解下列遞推關(guān)系式(1)假定的—t響=3T(n-l)=3(^r(n-2))=3f5(3T(?i-3)))==3^T(1)=4x芋T=-^=0(^):分治遞歸式'(")2T(m/3)4-nm>1va=2^ft=3,t=1j.a<bk根據(jù)通用遞婦式的定理徐T(M)—O(m^)—O(M)第3章蠻力法1、掌握蠻力法的設(shè)計思想：蠻力法依賴的基本技術(shù)——掃描技術(shù)，即采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解；關(guān)鍵——依次處理所有元素。2、蠻力法的代表算法及其時間復(fù)雜度：順序查找，O(n)串匹配(BFO(n*m)，KMPO(n+m)選擇排序，O(n2)冒泡排序，O(n2)生成排列對象(排列問題)，O(n!)生成子集(組合問題)，O(2n)0/1背包屬于組合問題。任務(wù)分配，哈密頓回路，TSP問題屬于排列問題。

3、掌握BF和KMP算法的原理，能夠畫出比較過程。要求給出一串字符串，能夠求出對應(yīng)的next數(shù)組，并能使用KMP算法進行比較匹配。4、掌握選擇排序和冒泡排序算法描述和時間復(fù)雜性，要求能夠?qū)懗鰝未a。選擇排序算法描述：選擇排序開始的時候，掃描整個序列，找到整個序列的最小記錄和序列中的第一記錄交換，從而將最小記錄放到它在有序區(qū)的最終位置上，然后再從第二個記錄開始掃描序列，找到n-1個序列中的最小記錄，再和第二個記錄交換位置。一般地，第i趟排序從第i個記錄開始掃描序列，在n-i+1個記錄中找到關(guān)鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。時間復(fù)雜性：O(n2)偽代碼：voidSelectSort(intr[]tin(ti)算法3,—選擇排序〃數(shù)組下標(biāo)從1并始|forvoidSelectSort(intr[]tin(ti)算法3,—選擇排序〃數(shù)組下標(biāo)從1并始|for(i=l;研)!in(1ex=i;；f°r(j=i+lij<=n;j++)；if(r[j|<r[indexl)index=j;|if(index!=i)r[i]-吁[ind瑚;。對B個記錄進行!H趟簡單選擇排序〃在無序區(qū)中我最小記錄J偌最小記錄不在最終位置則交換冒泡排序，O(n2)；算法3.7——起痼排序ivoidBubbhSort(intr[]Tintn)。數(shù)組下標(biāo)從1開始|far(i=l;i<=irl;i++)//i循壞用來實現(xiàn)比較的趟數(shù)，共需比n-1趟“-for(j=l;]++■)"j循環(huán)用來在-趟中兩兩相比『并換位』iifO1jP『[j+l]}r[j]JT[j+lh。如果反序，則交換元素:}i5、算法設(shè)計題：假設(shè)在文本“ababcabccabccacbab”中查找模式"abccac”,求分別采用BF算法和KMP算法進行串匹配過程中的字符比較次數(shù)。解；BF算法…第一泡IIIIahwb*ocabccabccacb豈b+jh-ffiabKa>Vtabcabccabccacbabi-1第二范ahabIIIIabC'beeabccacb豈b+J第四趟ababKau■A>cabeeabccacbab*第五越ababi21-TTabeeabccacbab第六憩ababcabeeIIIIIIabccaII*-cbab+J由此可知，用BF算法一共要進行3+1+4+1+1+6+1+1+1+6=25次比較方能匹配出KMP算法：next[]={,0,1,1,1,1,2};由此可知，用KMP算法一共要進行3+4+6+5=18次比較方能匹配出第4章分治法了解分治法的設(shè)計思想設(shè)計思想：將要求解的原問題劃分成k個較小規(guī)模的子問題，對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再將每個子問題劃分為k個規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足夠小，很容易求出其解為止，再將子問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原問題的解。步驟：(1)劃分(2)求解子問題(3)合并分治法的代表算法及時間復(fù)雜度：歸并排序，快速排序，最大子段和，最近對問題，這五種問題的分治算法的時間復(fù)雜度為O(nlog2n)棋盤覆蓋為O(4k)掌握歸并排序和快速排序算法的算法偽代碼。歸并排序：:京"航4.3二五赫誦^/voidMergeSoit(intr[].int],ints,intt)iifl==t)rl[s]=r[s]；Ielse{；m=:Merger"。*〃歸并排序前半個子序歹I；Mergesort3",m+Lt);〃歸并排序后半個子序|Merge(rl,r,m,t);〃合并兩個已排序的子序I「?算法中數(shù)組r中存儲原始數(shù)據(jù)，r1在中間過程中存儲排序后的數(shù)據(jù)，s指需排序數(shù)組的起始下標(biāo)，t指需排序數(shù)組的結(jié)束下標(biāo)。最終排序后的數(shù)據(jù)依然存儲在r數(shù)組中。I彰算法4.—合并有序子序列b/voidMerge(intr[intrlf]fints,intm,intt)k{..ii=s;j=m+l;k=s;|while(i<=m&&j<=t)iif(r[i]<=rUPrl[k++]=r[i++R〃取科i]和叩]中較小者放入以1【ielserl[k++]=i*U++];；if(i<=m)while(i〈=m)!〃若第一個子序列沒處理完，則進行收尾處理:11Jk++]=!*[!++]；；ekewhile(j<=t)；〃若第二個子序列沒處理完，則進行收尾處理Ii'l[k++]=r[j++];快速排序朝算法4.一次劃分\/intPartition(intr[],intfirst,intend)i=first;j=end;〃初始化while(i<j)while(i<j&&r[i]<=r[j])j一；〃右側(cè)掃描if(i<j){i?[i]--r[j];〃將較小記錄交換到前面i++;}while(i<j&&r[i]<=r[j])i++；〃左側(cè)掃描if(ivj){r[j]-->r[i];〃將較大記錄交換到后面}}retutni;〃i為軸值記錄的最終位置土TOC\o"1-5"\h\z項疝二福?！窺uicksort(intr[],intfirst,intend)；%；if(Iks心id){-phot=Partitiou(r,fiiwt,end);!|〃問題分解，piYOt是軸值在序列中的位置;QiiickSort(i\first,pivot-1);■I〃遞歸地對左側(cè)子序列進行快速排序:QuickSoil1上ph頃+Lend;i;I〃遞歸地對右倒子序列進行快速排序I}Li對于待排序列(5,3,1,9,8,2,4,7)，畫出快速排序的遞歸運行軌跡。按升序排列初始序列：5,3,1,9,8,2,4,7第一次劃分：4,3,1,2,5,8,9,7第二次劃分：2,3,1,4,5,8,9,7第三次劃分：1,2,3,4,5,8,9,7第四次劃分：1,2,3,4,5,7,8,9排序完成，紅色字體為每次劃分的軸值第5章減治法了解減治法的設(shè)計思想設(shè)計思想：原問題的解只存在于其中一個較小規(guī)模的子問題中，所以，只需求解其中一個較小規(guī)模的子問題就可以得到原問題的解。掌握使用減治法的代表問題及時間復(fù)雜度：折半查找，二叉樹查找，堆排序，選擇問題，淘汰賽冠軍問題，假幣問題；以上問題的時間復(fù)雜度，如果減治是每次減小為原來規(guī)模的1/2,則時間復(fù)雜度一般為O(log2n)掌握折半查找的算法偽代碼描述及具體例子的查找過程，會根據(jù)折半查找的過程創(chuàng)建判定樹。;段算法El——折半查找；LIqw-1：high=n：//設(shè)置初始查找區(qū)間:2?測試查找區(qū)間[low,high]是否存在，若不存在，則查找失敗:否則；3,取中間點mid-(low-i-high)12;比較k與r[mid],有以卜三種情況:；3.1若k<r[ini(l],則high=niidT；查找在左半?yún)^(qū)進行,轉(zhuǎn)、;3,2若k>r[niiil],則lo^-inid+1：母找在右半?yún)^(qū)進行丁轉(zhuǎn)2：偵)按6390=5齪70,4240,45,83,67(b)按55,42,10,70,63,58,83,67.90^的順序構(gòu)造的二又排序樹的順序構(gòu)造的二叉排序樹掌握堆排序算法中的兩種調(diào)整堆和新建堆的方法：篩選法堆調(diào)整問題：將一個無序序列調(diào)整為堆(1)篩選法調(diào)整堆關(guān)鍵問題：完全二叉樹中，根結(jié)點的左右子樹均是堆，如何調(diào)整根結(jié)點，使整個完全二叉樹成為一個堆？(時28與玷交換(b)28與32交換(c)將2瞬到葉子第6章動態(tài)規(guī)劃法了解動態(tài)規(guī)劃法的設(shè)計思想設(shè)計思想：將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解。步驟：將原始問題分解為相互重疊的子問題，確定動態(tài)規(guī)劃函數(shù)；求解子問題，填表；根據(jù)表，自底向上計算出原問題的解。掌握可以用動態(tài)規(guī)劃法解決的問題及時間復(fù)雜度：TSP，多段圖的最短路徑問題，0/1背包，最長公共子序列問題，最優(yōu)二叉查找樹，近似串匹配問題；多段圖的最短路徑問題：O(n+m)0/1背包問題：O(nxC)掌握多段圖的最短路徑問題的動態(tài)規(guī)劃算法y算法丘2——多段圖的最短路徑/1-初始也數(shù)組cost[n]初始化為最大值，數(shù)組網(wǎng)比回初始化為T；\2.for(i=ii-2;i>=0;i，-)；2.1對頂點i的每一個鄰接點j,根據(jù)式6.7計算匚0河正!2.2根據(jù)式6.8計算pmh[i];；5?輸出最短5&徑長^cGstfO];，4?輸出最短路徑經(jīng)過的頂點二；4J1=0i4.2循環(huán)直到path[i]=n-l-421輸th|)?itli|ij；).-■.■.■>_.^,,2.—.——.——.—.I—.—I.■._*工、■'—11—??動態(tài)規(guī)劃函數(shù)為：cost[i]中存儲頂點動態(tài)規(guī)劃函數(shù)為：cost[i]中存儲頂點i到終點的最短路徑長度cost[i]=min{C[i][j]+cost[j]}（i<j且頂點j是頂點i的鄰接點）path[i]=使C[i][j]+cost[j撮小的j先構(gòu)造cost數(shù)組和path數(shù)組一個多段圖0!116:172：34tJi15：13：95\6aaaJa9：87；8；7：3_；354\5:8I8倫：Q\9\掌握0/1背包問題的動態(tài)規(guī)劃算法及具體實現(xiàn)尹6：3二0萬普菰嗣'mtKnapSackfuitn.mtw[].mt\[]jifor(1=0;i<=n;i++)//初始化W。列iVri][0]=0;；for(j=0;|<=C:J++)〃初始化答。行IV[0][]]=0;ifor(i=l;K=n;i-^)〃計算第I行’進行第秋送代|foT(j=l；J<=C；|H)iif0<w[l])算法6.3―/I背包問題rv[i][j]=V[Fl]O)；ielse，V[i][j]=mg(V[i?l][j],V[iT][jf[i]]+v[i]);|j-C;〃求裝入背包的物品-for(i=n;i>0;i——)iehex[i]=O;-returnV[n][C]：〃返回背包取得的最大價值例題：用動態(tài)規(guī)劃法求如下0/1背包問題的最優(yōu)解：有5個物品，其重量分別為(3,2,1,4,5)，物品的價值分別為(25,20，15,40，50)，背包容量為6。寫出求解過程。0/1背包問題的動態(tài)規(guī)劃函數(shù)為:W)一叩-1J)J<叫max{7(z-l?/)?叩一拔-雄)+號V(i,j)表示把前i個物品放入容量為j的背包中的最大價值和。W)一填表過程：43^4^50山W0LOp25p25*22.W=2,v=20^—20p25p2d43/W=l,v=15^15-15p35-40#4W=4,v=40^Op15—15p35^40.b5村W=5,v=50.15.15p40,5放入背包中的物品的求解過程：則65表示把5個物品放入容量為6的背包中的最大價值和。i=5,j=6;v[5][6]>v[4][6],x[5]=1,j=6-w[5]=1i=4,j=1；v[4][1]=v[3][1],x[4]=0i=3,j=1；v[3][1]>v[2][1],x[3]=1,j=1-w[3]=0i=2,j=0；v[2][1]=v[1][0],x[2]=0i=1,j=0；v[1][0]=v[0][0],x[1]=0結(jié)果是把第3個和第5個放入了背包第7章貪心法了解貪心法的設(shè)計思想貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前巳有的信息就做出局部最優(yōu)選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。貪心法的關(guān)鍵在于決定貪心策略。掌握可以用貪心法解決的問題：TSP問題中的兩種解決方法：最近領(lǐng)點策略，最短鏈接策略最小生成樹問題的兩種算法：最近頂點策略（Prim算法），最短邊策略（Kruskal算法）背包問題，活動安排問題，多機調(diào)度問題。

掌握最小生成樹的兩種貪心算法：prim算法和kruskal算法（P145-148），給出具體的例子，能夠用兩種方法畫出樹的生成過程。I印)連通網(wǎng)，掌握最小生成樹的兩種貪心算法：prim算法和kruskal算法（P145-148），給出具體的例子，能夠用兩種方法畫出樹的生成過程。(c)U={A^.C)C0St={(4,引26](c)U={A^.C)C0St={(4,引26](d)U=(4凡UD}(e)U={47,C\dE}(f)g{A.FCD,匹5>Eim算法構(gòu)造最小生成樹的過程示意Kiu^l方法構(gòu)造最小生成樹的過程掌握背包問題的貪心算法(P148-151)，給出一個具體的例子，能夠?qū)懗鼋鉀Q問題的過程。習(xí)題7-2問題：求如下背包問題的最優(yōu)解：有7個物品，價值P=(10,5,15,7,6,18,3),重量w=(2,3,5,7,1,4,1),背包容量W=15.解決方法：先對物品物品重量的單位重量價值按照降序排列物品價值物品價值/物品重量16621054184.55153133351.67771依次把物品放入容量為15的背包，直到背包被裝滿1+2+4+5+1=13,前5個物品裝入背包，還剩下容量為2,第6個物品只能裝入2/3所以總價值為：6+10+18+15+3+5*2/3=55.3333第8章回溯法了解回溯法的設(shè)計思想設(shè)計思想：從解空間樹根結(jié)點出發(fā)，按照深度優(yōu)先策略遍歷解空間樹，在搜索至樹中任一結(jié)點時，先判斷該結(jié)點對應(yīng)的部分解是否滿足約束條件，或者是否超出目標(biāo)函數(shù)的界，也就是判斷該結(jié)點是否包含問題的（最優(yōu)）解，如果肯定不包含，則跳過對以該結(jié)點為根的子樹的搜索，即所謂剪枝（Pruning）；否則，進入以該結(jié)點為根的子樹，繼續(xù)按照深度優(yōu)先策略搜索。直到搜索到葉子結(jié)點，則得到問題的一個可能解。步驟：確定解向量和分量的取值范圍，構(gòu)造解空間樹；確定剪枝函數(shù)；對解空間樹按深度優(yōu)先搜索，搜索過程中剪枝；從所有的可能解中確定最優(yōu)解。了解可以用回溯法解決的問題：屬于組合問題和排列問題中求最優(yōu)解的問題都可以用回溯法解決，例如：圖著色問題，哈密頓回路問題，