算法分析的復(fù)習(xí)總結(jié)

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

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

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

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

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

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

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

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

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