1、算法分析與設計復習大綱第1章 緒論考點：1、  算法的5個重要特性。答：輸入、輸出、有窮性、確定性、可行性2、  掌握擴展遞歸技術和通用分治遞推式的使用。擴展遞歸技術：通用分支遞歸式：5、使用擴展遞歸技術求解下列遞推關系式（1）（2）第3章 蠻力法1、  掌握蠻力法的設計思想：蠻力法依賴的基本技術掃描技術，即采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解;關鍵依次處理所有元素。2、  蠻力法的代表算法及其時間復雜度：順序查找，O(n)串匹配（BF O(n*m) ，KMPO(n+m)  選擇排序，O(n2)

2、冒泡排序，O(n2)生成排列對象（排列問題），O(n!)生成子集（組合問題），O(2n)0/1背包 屬于組合問題。任務分配，哈密頓回路，TSP問題 屬于排列問題。3、  掌握BF和KMP算法的原理，能夠畫出比較過程。要求給出一串字符串，能夠求出對應的next數組，并能使用KMP算法進行比較匹配。4、  掌握選擇排序和冒泡排序算法描述和時間復雜性，要求能夠寫出偽代碼。選擇排序算法描述：選擇排序開始的時候，掃描整個序列，找到整個序列的最小記錄和序列中的第一記錄交換，從而將最小記錄放到它在有序區的最終位置上，然后再從第二個記錄開始掃描序列，找到n-1個序列中的最小記錄，再和第二個

3、記錄交換位置。一般地，第i趟排序從第i個記錄開始掃描序列，在n-i+1個記錄中找到關鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。時間復雜性：O(n2)偽代碼：冒泡排序算法描述：冒泡排序開始的時候掃描整個序列，在掃描過程中兩兩比較相鄰記錄，如果反序則交換，最終，最大記錄就能被“沉到”了序列的最后一個位置，第二趟掃描將第二大記錄“沉到”了倒數第二個位置，重復上述操作，直到n-1趟掃描后，整個序列就排好序了。冒泡排序，O(n2)5、  算法設計題： 假設在文本“ababcabccabccacbab”中查找模式 “abccac”,求分別采用BF算法和KMP算法進行串匹配過程中

4、的字符比較次數。由此可知，用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章  分治法了解分治法的設計思想設計思想：將要求解的原問題劃分成k個較小規模的子問題，對這k個子問題分別求解。如果子問題的規模仍然不夠小，則再將每個子問題劃分為k個規模更小的子問題，如此分解下去，直到問題規模足夠小，很容易求出其解為止，再將子問題的解合并為一個更大規模的問題的解，自底向上逐步求出原問題的解。步驟：（1）劃分（2）求解子問題（3）合并分治法的代表算

5、法及時間復雜度：歸并排序，快速排序，最大子段和，最近對問題，這五種問題的分治算法的時間復雜度為O(nlog2n)棋盤覆蓋為O(4k)掌握歸并排序和快速排序算法的算法偽代碼。歸并排序：算法中數組r中存儲原始數據，r1在中間過程中存儲排序后的數據，s指需排序數組的起始下標，t指需排序數組的結束下標。最終排序后的數據依然存儲在r數組中。快速排序：對于待排序列（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

6、,9,7第四次劃分：1,2,3,4,5,7,8,9排序完成，紅色字體為每次劃分的軸值 第5章 減治法了解減治法的設計思想設計思想：原問題的解只存在于其中一個較小規模的子問題中，所以，只需求解其中一個較小規模的子問題就可以得到原問題的解。掌握使用減治法的代表問題及時間復雜度：折半查找，二叉樹查找，堆排序，選擇問題，淘汰賽冠軍問題，假幣問題；以上問題的時間復雜度，如果減治是每次減小為原來規模的1/2，則時間復雜度一般為O(log2n)掌握折半查找的算法偽代碼描述及具體例子的查找過程，會根據折半查找的過程創建判定樹。會根據已知數據序列創建一個二叉查找樹。（P100）掌握堆排序算法中的兩種調

7、整堆和新建堆的方法：篩選法堆調整問題：將一個無序序列調整為堆（1）篩選法調整堆        關鍵問題：完全二叉樹中，根結點的左右子樹均是堆，如何調整根結點，使整個完全二叉樹成為一個堆？    第6章 動態規劃法了解動態規劃法的設計思想設計思想：將待求解問題分解成若干個相互重疊的子問題，每個子問題對應決策過程的一個階段，將子問題的解求解一次并填入表中，當需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解。步驟：將原始問題分解為相互重疊的子問題，確定動態規劃函數；求解子問題，填表；

8、根據表，自底向上計算出原問題的解。掌握可以用動態規劃法解決的問題及時間復雜度：TSP，多段圖的最短路徑問題，0/1背包，最長公共子序列問題，最優二叉查找樹，近似串匹配問題；多段圖的最短路徑問題： O(n+m)0/1背包問題： O(n×C)掌握多段圖的最短路徑問題的動態規劃算法動態規劃函數為：costi中存儲頂點i到終點的最短路徑長度costi=minCij+costj (ijn且頂點j是頂點i的鄰接點)pathi=使Cij+costj最小的j先構造cost數組和path數組掌握0/1背包問題的動態規劃算法及具體實現例題：用動態規劃法求如下0/1背包問題的最優解：有5個物品，其重量分別

9、為（3，2，1，4，5），物品的價值分別為（25，20，15，40， 50），背包容量為6。寫出求解過程。0/1背包問題的動態規劃函數為：V(i,j)表示把前i個物品放入容量為j的背包中的最大價值和。填表過程：放入背包中的物品的求解過程：則65表示把5個物品放入容量為6的背包中的最大價值和。i=5,j=6;  v56>v46,x5=1, j=6-w5=1i=4,j=1; v41=v31, x4=0i=3,j=1; v31>v21, x3=1, j=1-w3=0i=2,j=0; v21=v10, x2=0i=1,j=0; v10=v0

10、0, x1=0結果是把第3個和第5個放入了背包第7章 貪心法了解貪心法的設計思想貪心法在解決問題的策略上目光短淺，只根據當前已有的信息就做出局部最優選擇，而且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。貪心法的關鍵在于決定貪心策略。掌握可以用貪心法解決的問題：TSP問題中的兩種解決方法：最近領點策略，最短鏈接策略最小生成樹問題的兩種算法：最近頂點策略（Prim算法），最短邊策略（Kruskal算法）背包問題，活動安排問題，多機調度問題。掌握最小生成樹的兩種貪心算法：prim算法和kruskal算法（P145-148），給出具體的例子，能夠用兩種方法畫出樹的生成過程。掌握背包問題的貪

11、心算法（P148-151），給出一個具體的例子，能夠寫出解決問題的過程。習題7-2問題：求如下背包問題的最優解：有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章 回溯法了解回溯法的設計思想設計

12、思想：從解空間樹根結點出發，按照深度優先策略遍歷解空間樹，在搜索至樹中任一結點時，先判斷該結點對應的部分解是否滿足約束條件，或者是否超出目標函數的界，也就是判斷該結點是否包含問題的（最優）解，如果肯定不包含，則跳過對以該結點為根的子樹的搜索，即所謂剪枝（Pruning）；否則，進入以該結點為根的子樹，繼續按照深度優先策略搜索。直到搜索到葉子結點，則得到問題的一個可能解。步驟：確定解向量和分量的取值范圍，構造解空間樹；確定剪枝函數；對解空間樹按深度優先搜索，搜索過程中剪枝；從所有的可能解中確定最優解。了解可以用回溯法解決的問題：屬于組合問題和排列問題中求最優解的問題都可以用回溯法解決，例如：圖著

13、色問題，哈密頓回路問題，八皇后問題（4皇后問題），批處理作業調度問題。掌握m顏色圖著色判定問題的回溯法算法，并能畫出解空間樹的搜索過程（P168-170），習題8-4對圖8.14使用回溯法求解圖問題，畫出生成的搜索空間。解：圖著色問題求解的是滿足圖著色要求的最小顏色數。對圖8.14應該從1、2、3、4種顏色依次嘗試用回溯法判定是否滿足M著色的要求。經搜索，1種和2種顏色均不能滿足圖著色的要求，3種顏色可以滿足圖著色要求，搜索過程如下，所以圖8.14的著色的最少顏色數應該為3搜索空間為：掌握0/1背包問題的回溯算法，并能畫出解空間樹的搜索過程掌握圖著色問題的回溯算法，并能畫出解空間樹的搜索過程第9章 分治限界法了解分支限界法的設計思想設計思想：1）首先確定一個合理的限界函數，并根據限界函數確定目標函數的界down, up ，并確定限界函數；2）然后按照廣度優先策略遍歷問題的解空間樹，在分支結點上，依次搜索該結點的所有孩子結點，分別估算這些孩子結點的限界函數的可能取值；3）如果某孩子結點的限界函數可能取得的值超出目標函數的界，則將其丟棄；否則，將其加入待處理結點表（以下簡稱表PT）中；4）依次從表PT中選取使限界函數的值是極值的結點成為當前擴展結點；5）重復上述過程，直到找到搜索到葉子結點，如果葉子結