算法復(fù)習(xí)易錯(cuò)點(diǎn)總結(jié)

1、一、判斷題（F）一個(gè)完全多項(xiàng)式近似方案是一個(gè)近似方案A，其中每一個(gè)算法A，在輸入實(shí)例I的規(guī)模的多項(xiàng)式時(shí)間內(nèi)運(yùn)行。（F）若近似算法A求解某極小化問(wèn)題一實(shí)例的解為s，且已知該問(wèn)題的最優(yōu)解為s/3，則該近似算法的性能比為3。（Y）若P2多項(xiàng)式時(shí)間轉(zhuǎn)化為P1，則P2至少與P1一樣難。（F）快速排序算法的平均時(shí)間復(fù)雜度是O（nlogn），使用隨機(jī)化快速排序算法可以將平均時(shí)間復(fù)雜度降得更低。（Y）若f（n）=O（g（n），則g（n）=Omiga（f（n）。（Y）類似這種關(guān)系均成立。（T）O(f(n)+O(g(n) = O(maxf(n),g(n)（F）隨機(jī)化快速排序的worst case 出現(xiàn)于輸入數(shù)組恰

2、好為已按非降序排列的情況（假設(shè)輸出的排序結(jié)果也要求是非降序）。（出現(xiàn)在所有數(shù)都相同的情況下）二、問(wèn)答題1、二叉查找樹屬于減治策略的三個(gè)變種中哪一個(gè)應(yīng)用？什么情況下二叉查找樹表現(xiàn)出最差的效率？此時(shí)的查找和插入算法的復(fù)雜性如何？答：減可變規(guī)模；樹是嚴(yán)格歪斜的情況下，效率最差；此時(shí)查找和插入效率均為大theta（n）。2、構(gòu)造AVL樹和2-3樹的主要目的是什么？它們各自有什么樣的查找和插入的效率？答：二叉查找樹僅在平均情況下效率比較高，為了彌補(bǔ)這一缺點(diǎn)，產(chǎn)生了這兩種方案。能使樹的左右子樹更加平衡，目的是減小樹的層數(shù)，使平均搜索效率更高。AVL：最差情況下，查找和插入操作的效率屬于(lgn)。2-3樹

3、：無(wú)論在最差情況還是在平均情況，查找、插入和刪除的時(shí)間效率都屬于（log n)。3、寫出0/1背包問(wèn)題的一個(gè)多項(xiàng)式等價(jià)的判定問(wèn)題，并說(shuō)明為什么它們是多項(xiàng)式等價(jià)的。答：是否存在價(jià)值至少為k的可行解。若原問(wèn)題有多項(xiàng)式時(shí)間內(nèi)的算法可以解決，則該判定問(wèn)題有解。若判定問(wèn)題在多項(xiàng)式時(shí)間內(nèi)有解，原問(wèn)題也可以轉(zhuǎn)化為判定問(wèn)題。因此成為多項(xiàng)式等價(jià)。4、何謂偽多項(xiàng)式算法？如何將一Monte Carlo算法轉(zhuǎn)化為L(zhǎng)as Vegas算法？以子集和問(wèn)題為例說(shuō)明偽多項(xiàng)式時(shí)間算法 和FPAS可以有的關(guān)系。答：?jiǎn)胃怕蕿?的Monte Carlo算法就是Las Vegas算法。算法的時(shí)間復(fù)雜度是輸入數(shù)據(jù)的多項(xiàng)式表達(dá)，但卻是輸入數(shù)

4、據(jù)長(zhǎng)度的指數(shù)時(shí)間表達(dá)。一個(gè)完全多項(xiàng)式近似方案（FPAS）是一個(gè)近似方案A， 其中每個(gè)算法A在以輸入實(shí)例的規(guī)模和1/兩者的多項(xiàng)式時(shí)間內(nèi)運(yùn)行。偽多項(xiàng)式時(shí)間算法是一種算法，它在L值的多項(xiàng)式時(shí)間內(nèi)運(yùn)行，其中L是輸入實(shí)例中的最大數(shù)值。為NP難問(wèn)題找到一個(gè)FPAS的想法對(duì)存在偽多項(xiàng)式時(shí)間算法的問(wèn)題來(lái)說(shuō)是很典型的。子集和問(wèn)題是背包問(wèn)題的特例，就是在背包問(wèn)題中各項(xiàng)的值和它們的重量（尺寸）相同：給出大小為s1, s2, , sn的n個(gè)項(xiàng)和背包容量正整數(shù)C， 找出這些項(xiàng)的一個(gè)子集，使得它們大小的總和最大化，且不超過(guò)背包的容量C。5、下面問(wèn)題是否屬于NP問(wèn)題？為什么？給定圖G=（N，A）中的兩個(gè)點(diǎn)p、q，整數(shù)c和t

5、，圖G中每條邊的長(zhǎng)度cij及遍歷這條邊的時(shí)間tij，問(wèn)圖G中是否存在一條由p到q的路徑，使得其長(zhǎng)度大于C，且遍歷時(shí)間小于t？答：屬于NP問(wèn)題，因?yàn)閷?duì)該問(wèn)題的每一個(gè)肯定實(shí)例，均存在一個(gè)多項(xiàng)式時(shí)間內(nèi)的驗(yàn)證。6、簡(jiǎn)述Las Vegas算法和Monte Carlo算法的主要區(qū)別。答：前者不一定總能給出解，但給出的解一定是正確的。后者總能給出解，但是給出的解可能是錯(cuò)誤的。7、基于比較的尋找數(shù)組A中最大最小元素問(wèn)題的最緊的下界答：3n/2-28、請(qǐng)給出基于比較的對(duì)數(shù)組A進(jìn)行排序問(wèn)題的最緊的下界，并寫出兩個(gè)平均時(shí)間復(fù)雜度為該下界的排序算法的名稱。答：O（nlogn），快速排序和隨機(jī)化的快速排序。9、說(shuō)一個(gè)有

6、最優(yōu)解的貪心算法答：最短路徑，DIJKSTRA，哈夫曼編碼10、說(shuō)出兩個(gè)NP問(wèn)題答：電路可滿足性問(wèn)題，布爾公式可滿足性問(wèn)題，3合取范式的布爾公式的可滿足性問(wèn)題，團(tuán)問(wèn)題，頂點(diǎn)覆蓋問(wèn)題，哈密頓回路問(wèn)題，TSP問(wèn)題，子集和問(wèn)題。11、請(qǐng)列舉三種求問(wèn)題下界的方法。答：計(jì)數(shù)論證法和歸約方法。三、算法分析題1、迪杰斯特拉算法時(shí)間復(fù)雜度O（n2）；2、多數(shù)問(wèn)題，比較其蠻力算法，并用變治思想求解。答：蠻力O（n2）。變治思想，進(jìn)行預(yù)排序。時(shí)間復(fù)雜度O（nlogn）。O（n）時(shí)間效率的解法是：隨機(jī)化算法提示：任取兩個(gè)元素，如果不相同，則同時(shí)拋棄。3、P:We say that a recognition pro

7、blem P1 belongs to class P if some polynomial-time algorithm solves problem P1. 存在求解判定問(wèn)題P1的多項(xiàng)式算法.NP:Roughly speaking, we say that a recognition problem P1 is in the class NP, if for every yes instance I of P1, there is a short (i.e., polynomial length) verification that the instance is a yes instanc

8、e.對(duì)P1的每一個(gè)肯定實(shí)例，均存在一個(gè)多項(xiàng)式時(shí)間內(nèi)的驗(yàn)證。P1中所有問(wèn)題均屬于NP.NPC:A recognition problem P1 is said to be NP-complete if :1) P1NP, and all other problems in the class NP polynomially transform to P1.2) NP中其它所有問(wèn)題多項(xiàng)式轉(zhuǎn)化為P1NP-Hard: A recognition problem P1 is said to be NP-hard if all other problems in the class NP polynomially reduce to P1. The class NP-hard is broader than the class NP-complete because it includes the class NP as well as problems that are not i