算法分析的復習總結

1、遞歸：直接或間接的調用自身算法稱為遞歸算法；用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治法（divide-and-conquer）的基本思想：A分割成k個更小規(guī)模的子問題。B對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。C將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。設計動態(tài)規(guī)劃算法的步驟(1)找出最優(yōu)解的性質，并刻劃其結構特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的

2、方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。最優(yōu)子結構性質：矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質貪心算法: 貪心算法總是作出在當前看來最好的選擇,它并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。貪心算法：貪心算法求解的這類問題一般具有2個重要的性質：貪心選擇性質和最優(yōu)子結構性質。 貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)

3、的選擇，即貪心選擇來達到。當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質貪心算法與動態(tài)規(guī)劃算法的差異：貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是2類算法的一個共同點。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。0-1背包問題：給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?單源最短路徑基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于

4、集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度?；厮莘ǖ幕舅枷耄?1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常見的兩種分支限界法：（1）隊列式(FIF

5、O)分支限界法。按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。（2）優(yōu)先隊列式分支限界法。按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。布線問題算法思想：解此問題的隊列式分支限界法從起始位置a開始將它作為第一個擴展結點。與該擴展結點相鄰并且可達的方格成為可行結點被加入到活結點隊列中，并且將這些方格標記為1，即從起始方格a到這些方格的距離為1。接著，算法從活結點隊列中取出隊首結點作為下一個擴展結點，并將與當前擴展結點相鄰且未標記過的方格標記為2，并存入活結點隊列。這個過程一直繼續(xù)到算法搜索到目標方格b或活結點隊列為空時為止。即加入剪枝的廣度優(yōu)先搜索。隨機存儲機RAM

6、它描述的形式計算機是一臺帶累加器計算機，他不允許程序修改其自身，RAM由只讀輸入帶、只寫輸入帶、程序存儲部件、內存儲器和指令計數(shù)器5個部分組成。 P類和NP類語言的定義P=L|L是一個能在多項式時間內被一臺DTM所接受的一眼 NP+L|L是一個能在多項式時間內被一臺NDTM所接受的語言 由于一臺確定性圖靈機可看作是非確定性圖靈機的特例，所以可在多項式時間內被非確定性圖靈機接受。故P屬于NP P類問題：是確定性計算模型下的易解問題類。NP類問題：是非確定性計算模型下的易驗證問題類。NP完全類問題：即多項式復雜度的非確定性問題類；簡單的寫法是NP=P？問題就在這個問號上，到底是NP等于P，還是NP

7、不等于P。 算法的漸進時間復雜性的含義？答：當問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(階)評價算法。時間復雜度T(n)的數(shù)量級(階)稱為漸進時間復雜性。最壞情況下的時間復雜性和平均時間復雜性有什么不同？答：最壞情況下的時間復雜性和平均時間復雜性考察的是n固定時，不同輸入實例下的算法所耗時間。最壞情況下的時間復雜性取的輸入實例中最大的時間復雜度：W(n) = max T(n，I) , IDn A(n) =P(I)T(n，I) IDn平均時間復雜性是所有輸入實例的處理時間與各自概率的乘積和：采用回溯法求解

8、的問題，其解如何表示？有什么規(guī)定？問題的解可以表示為n元組：（x1,x2,xn），xiSi, Si為有窮集合，xiSi, （x1,x2,xn）具備完備性，即（x1,x2,xn）是合理的，則（x1,x2,xi）(i<n)一定合理。簡述漸進時間復雜性上界的定義。T(n)是某算法的時間復雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C，nNo，有T(n)<f(n)，這種關系記作T(n)=O(f(n)?？焖倥判虻幕舅枷胧鞘裁础？焖倥判虻幕舅枷胧窃诖判虻腘個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關鍵字比該記錄關鍵字小的放在前一部分，所有比它大的

9、放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復上述過程，直到每一部分內只有一個記錄為止。 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結構？在定義一個過程或者函數(shù)的時候又出現(xiàn)了調用本過程或者函數(shù)的成分，既調用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調用過程或者函數(shù)Q，Q又調用P，這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結構。 哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。前綴碼：對每一個字符規(guī)定一個0,1串作為其代

10、碼，并要求任一字符的代碼都不是其他字符代碼的前綴。二、遞歸與分治：二分搜索算法：public static int binarySearch(int a, int x, int n) left = 0; right = n - 1; while (left <= right) int middle = (left + right)/2; if (x = amiddle) return middle; if (x > amiddle) left = middle + 1; else right = middle - 1; return -1; 棋盤覆蓋public void ches

11、sBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, s = size/2; if (dr < tr + s && dc < tc + s) chessBoard(tr, tc, dr, dc, s); else boardtr + s - 1tc + s - 1 = t; chessBoard(tr, tc, tr+s-1, tc+s-1, s); if (dr < tr + s && dc >= tc + s) che

12、ssBoard(tr, tc+s, dr, dc, s); else boardtr + s - 1tc + s = t; chessBoard(tr, tc+s, tr+s-1, tc+s, s); if (dr >= tr + s && dc < tc + s) chessBoard(tr+s, tc, dr, dc, s); else boardtr + stc + s - 1 = t; chessBoard(tr+s, tc, tr+s, tc+s-1, s); if (dr >= tr + s && dc >= tc + s)

13、chessBoard(tr+s, tc+s, dr, dc, s); else boardtr + stc + s = t; chessBoard(tr+s, tc+s, tr+s, tc+s, s); 三、動態(tài)規(guī)劃最長公共子序列void LCSLength(int m，int n，char x，char y，intc，int b) int i，j;for (i = 1; i <= m; i+) ci0 = 0; for (i = 1; i <= n; i+) c0i = 0; for (i = 1; i <= m; i+) for (j = 1; j <= n; j+

14、) if (xi=yj) cij=ci-1j-1+1; bij=1;else if (ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 構造最長公共子序列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return;if (bij= 1) LCS(i-1，j-1，x，b); cout<<xi; else if (bij= 2) LCS(i-1，j，x，b);else LCS(i，j-1，x，b); 最優(yōu)裝載void Loading(int x, Type w,

15、 Type c, int n)int *t = new int n+1; Sort(w, t, n);for (int i = 1; i <= n; i+) xi = 0; for (int i = 1; i <= n && wti <= c; i+) xti = 1; c -= wti;五、回溯法裝載問題void backtrack (int i) if (i > n) r -= wi; if (cw + wi <= c) xi = 1; cw += wi; backtrack(i + 1); cw -= wi; if (cw + r >

16、bestw) xi = 0; backtrack(i + 1); r += wi; 批處理問題：void Flowshop:Backtrack(int i)if (i > n) for (int j = 1; j <= n; j+)bestxj = xj; bestf = f;else for (int j = i; j <= n; j+) f1+=Mxj1; f2i=(f2i-1>f1)?f2i-1:f1)+Mxj2;f+=f2i; if (f < bestf) Swap(xi, xj); Backtrack(i+1);Swap(xi, xj); f1- =Mxj1; f- =f2i;六、分支限界法單源最短路徑問題while (true) for (i