算法分析總復(fù)習(xí)

優(yōu)選文檔算法解析總復(fù)習(xí)考試題型：填空、簡(jiǎn)答、編程、計(jì)算。算法的定義：依照某種機(jī)械步驟獲得問(wèn)題結(jié)果的辦理過(guò)程。算法的3要素：操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)。算法的3個(gè)結(jié)構(gòu)：序次結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法的基本性質(zhì)：目的性、分布性、有序性、有限性、操作性。算法的基本特點(diǎn)：有窮性、確定性、可行性、輸入性、輸出性。(前3個(gè)是最主要的)算法的(質(zhì)量)指標(biāo)：正確性、可讀性、莊重性、高效率與低儲(chǔ)藏量需求。算法的抽象描述：算法=控制結(jié)構(gòu)+原操作算法的表示方式包括：自然語(yǔ)言、流程圖、盒圖、PAD圖、偽代碼、程序設(shè)計(jì)語(yǔ)言。算法解析的任務(wù)：利用數(shù)學(xué)工具，談?wù)撍惴ǖ膹?fù)雜度。談?wù)撍惴ǖ臉?biāo)準(zhǔn)：算法實(shí)現(xiàn)所耗資的時(shí)間；算法實(shí)現(xiàn)所耗資的儲(chǔ)藏空間；算法應(yīng)易于理解、易于編碼、易于調(diào)試。算法復(fù)雜度：算法的時(shí)間復(fù)雜度與算法的空間復(fù)雜度的統(tǒng)稱。算法時(shí)間復(fù)雜度的估計(jì)：算法的執(zhí)行時(shí)間=v原操作的執(zhí)行次數(shù)X原操作的執(zhí)行時(shí)間算法時(shí)間復(fù)雜度的數(shù)量級(jí)的形式：①0(L)稱為常數(shù)級(jí)；②O(Logn)稱為對(duì)數(shù)級(jí)；③0(n)稱為線性級(jí)；④0(nc)稱為多項(xiàng)式級(jí)；⑤0(Cn)稱為指數(shù)級(jí)；⑥0(n!)稱為階乘級(jí);判斷時(shí)間復(fù)雜度的數(shù)量級(jí)：1)序次結(jié)構(gòu)的算法的時(shí)間復(fù)雜度是0(L)；2)循環(huán)結(jié)構(gòu)的算法的時(shí)間復(fù)雜度是0(nx)(x:循環(huán)的層數(shù))；算法時(shí)間復(fù)雜度的最壞情況：可操作性最好的，且最有實(shí)質(zhì)價(jià)值的，是最壞情況下的時(shí)間復(fù)雜性。算法的儲(chǔ)藏量包括：1)輸入數(shù)據(jù)所占空間；2)算法自己所占空間；3)輔助變量所占空間。NP完好問(wèn)題：多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題，是圖靈機(jī)在P時(shí)間內(nèi)解決的問(wèn)題，是世界7大數(shù)學(xué)優(yōu)選文檔優(yōu)選文檔難題之一。遞歸算法設(shè)計(jì)：就是把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)變成一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題，漸漸求解小問(wèn)題后，再返回獲得大問(wèn)題的解。遞歸與非遞歸的比較程序可讀性代碼量大小時(shí)間占用空間使用范圍設(shè)計(jì)難度遞歸易小長(zhǎng)大廣易非遞歸難大短小窄難算法與數(shù)據(jù)結(jié)構(gòu)：1）計(jì)算機(jī)辦理的問(wèn)題種類:數(shù)值計(jì)算問(wèn)題、非數(shù)值性問(wèn)題。2）算法設(shè)計(jì)的實(shí)質(zhì)：對(duì)實(shí)責(zé)問(wèn)題要辦理的數(shù)據(jù)選擇一種合適的儲(chǔ)藏結(jié)構(gòu)，并在選定的儲(chǔ)藏結(jié)構(gòu)上設(shè)計(jì)一個(gè)好的算法，實(shí)現(xiàn)對(duì)數(shù)據(jù)的辦理。好的算法在很大程度上取決于問(wèn)題中數(shù)據(jù)所采用的數(shù)據(jù)結(jié)構(gòu)。3）常用的數(shù)據(jù)結(jié)構(gòu)的分類：連續(xù)儲(chǔ)藏、鏈?zhǔn)絻?chǔ)藏。4）連續(xù)儲(chǔ)藏和鏈?zhǔn)絻?chǔ)藏的優(yōu)缺點(diǎn)比較：①基于儲(chǔ)藏的考慮：序次表的儲(chǔ)藏空間是靜態(tài)分配的，早先必定明確規(guī)定其儲(chǔ)藏規(guī)模；鏈表不用早先估計(jì)儲(chǔ)藏規(guī)模，但儲(chǔ)藏密度較低。②基于運(yùn)算的考慮：運(yùn)算若挨次號(hào)接見數(shù)據(jù)元素，則序次表優(yōu)于鏈表；若是比較操作，則鏈表優(yōu)于序次表。③基于環(huán)境的考慮：序次表簡(jiǎn)單實(shí)現(xiàn)；鏈表的操作是基于指針的?？傊?，平時(shí)較牢固的線性表選擇序次儲(chǔ)藏；而動(dòng)向性較強(qiáng)的線性表宜選擇鏈?zhǔn)絻?chǔ)藏。選學(xué)生會(huì)主席問(wèn)題（P70）的算法解析：先為5個(gè)候選人設(shè)置5個(gè)計(jì)數(shù)器，爾后依照選票分別對(duì)5個(gè)計(jì)數(shù)器累加1。即數(shù)組用于儲(chǔ)藏統(tǒng)計(jì)結(jié)果，而其下標(biāo)則是輸入的原始信息。編程統(tǒng)計(jì)身高問(wèn)題（P71）的算法解析：由于多數(shù)統(tǒng)計(jì)區(qū)間的大小都固定為5,這樣用“身高/5?29”做下標(biāo)，只須開辟8個(gè)元素的數(shù)組，對(duì)應(yīng)8個(gè)統(tǒng)計(jì)品位，即可達(dá)成統(tǒng)計(jì)工作。統(tǒng)計(jì)3科全及格的學(xué)生問(wèn)題（P71）的算法解析：從語(yǔ)文名單中逐一抽出及格學(xué)生學(xué)號(hào)，先在代數(shù)名單中查找，若有該學(xué)號(hào)，則代數(shù)也及格了，再在外語(yǔ)名單中查找，看該學(xué)號(hào)可否外語(yǔ)也及格了，若仍在，則該學(xué)號(hào)學(xué)生3科全及格，否則最少有一科不及格。語(yǔ)文名單中沒(méi)有的學(xué)號(hào)，不可以能3科全及格，所以，語(yǔ)文名單辦理完后算法就可以結(jié)束了。數(shù)字編號(hào)翻譯成英文編號(hào)問(wèn)題（P73）的算法解析：將英文的“zero?nine”儲(chǔ)藏在數(shù)組中，對(duì)應(yīng)下標(biāo)為“0?9”。經(jīng)過(guò)求余、取整運(yùn)算，可以取到編號(hào)的各個(gè)位數(shù)字。用這個(gè)數(shù)字作下標(biāo)，正好能找到對(duì)應(yīng)的英文數(shù)字。高精度數(shù)據(jù)X長(zhǎng)整數(shù)問(wèn)題（P78）的算法解析：一個(gè)高精度數(shù)據(jù)與一個(gè)自然數(shù)的乘法運(yùn)算過(guò)程，用一重循環(huán)來(lái)實(shí)現(xiàn)，循環(huán)變量i代表當(dāng)前參加運(yùn)算的數(shù)組下標(biāo)，d表示儲(chǔ)藏進(jìn)位。統(tǒng)計(jì)50個(gè)學(xué)生中最少有3門成績(jī)高于90分的人數(shù)問(wèn)題（P91）的算法解析：優(yōu)選文檔優(yōu)選文檔對(duì)每個(gè)同學(xué)，先計(jì)算其成績(jī)高于90分的課程科目，若高出3,則累加到滿足條件的人數(shù)中。用二重循環(huán)實(shí)現(xiàn)以上過(guò)程，外層循環(huán)模擬50個(gè)同學(xué)，內(nèi)層循環(huán)模擬5門課程。開燈問(wèn)題（P92）的算法解析：定義有n個(gè)元素的a數(shù)組，它的每個(gè)下標(biāo)變量a[i]視為一燈，i表示其編號(hào)。a[i]=1表示第i盞燈處于打開狀態(tài)，a[i]=0表示第i盞燈處于關(guān)閉狀態(tài)。經(jīng)過(guò)算術(shù)運(yùn)算a[i]=1-a[i]，就能很好地模擬開關(guān)燈的操作。數(shù)字圓圈問(wèn)題（P93）的算法解析：數(shù)組定義為a[n]，則有a[0]?a[n-1]共n個(gè)元素。用i代表下標(biāo)，題目就是序次將a（i-1）與a（i+1）相乘，經(jīng)過(guò)求余運(yùn)算求出乘積的最大值和最小值。任意3個(gè)數(shù)的最小公倍數(shù)問(wèn)題（P97和P136）的算法解析：用蠻力法最方便，但運(yùn)算時(shí)間最長(zhǎng)。警察抓小偷問(wèn)題（P99）的算法解析：將a、b、c、d4個(gè)人進(jìn)行編號(hào)，號(hào)碼分別是1、2、3、4。接著用列舉法來(lái)解決。老師展望數(shù)學(xué)競(jìng)賽問(wèn)題（P100）的算法解析：利用三重循環(huán)把所有的情況列舉出來(lái)即可。找次品問(wèn)題（P102）的算法解析：1?10號(hào)箱取產(chǎn)品的件數(shù)分別為20?29件，爾后稱量，就可以很簡(jiǎn)單地找到次品。數(shù)學(xué)模型的定義：數(shù)學(xué)模型是利用數(shù)學(xué)語(yǔ)言模擬現(xiàn)實(shí)的模型。把現(xiàn)實(shí)模型抽象、簡(jiǎn)化為某種數(shù)學(xué)結(jié)構(gòu)是數(shù)學(xué)模型的基本特點(diǎn)。上樓梯問(wèn)題（P114）的算法解析：設(shè)n階臺(tái)階的走法數(shù)位f（n）,則：仁n=1f(n)=2.................................................n=2f(n-1)f(n-2)n2迭代法的定義：也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值推出新值的解決問(wèn)題的方法。兔子生殖問(wèn)題（P124）的算法解析：把a(bǔ),b表示成每個(gè)月的前2個(gè)月和前1個(gè)月的兔子的對(duì)數(shù)，它們的初值均為1,這樣3月兔子的對(duì)數(shù)c=a+b;求4月兔子的對(duì)數(shù)時(shí)，先將4月前2個(gè)月和前1個(gè)月兔子的對(duì)數(shù)儲(chǔ)藏在變量a,b中，即a=b,b=c,再將4月份兔子的對(duì)數(shù)連續(xù)保留在變量c中，即c=a+b+當(dāng)然，在變量中的數(shù)據(jù)被覆蓋從前應(yīng)先行輸出已求解的結(jié)果。main（）{inti,a=1,b=1;printf（%d%d",a,b）;fot（i=1;i<=10;i++）{c=a+b;printf（“%d”,c）;a=b;b=c;優(yōu)選文檔優(yōu)選文檔}}倒推法的定義：是對(duì)某些特別問(wèn)題，所采用的從后向前推解的方法。楊輝三角(限制用1個(gè)一維數(shù)組達(dá)成)問(wèn)題(P)的算法解析：從每一行第i個(gè)元素倒著向前計(jì)算，則可防備這種情況出現(xiàn)迭代表達(dá)式以下：A[1]=A[i]=1;A[j](i行)=A[j](i-1行)+A[j-1](i-1行)j=i-1,i-2,,2;穿越沙漠問(wèn)題(P128)的算法解析：倒著累加儲(chǔ)油點(diǎn)間的距離，并計(jì)算各儲(chǔ)油點(diǎn)的儲(chǔ)油量，直到總距離高出1000千米，求解距出發(fā)點(diǎn)近來(lái)的一個(gè)儲(chǔ)油點(diǎn)的地址及儲(chǔ)油量，問(wèn)題就得以解決。牛頓迭代法的定義：又稱切線法，第一，選擇一個(gè)湊近f(X)零點(diǎn)的X。，計(jì)算相應(yīng)的f(Xo)的切線斜率f'(Xo);爾后，依照牛頓迭代公式Xn.1=Xn-f,(Xn)求得x1。該方法擁有更高收斂速度。f(Xn)二分逼近法的定義：a。+b0f(X)在區(qū)間[a,b]上連續(xù)，f(a)*f(b)<0。令[a。,bo]=[a,b],c000，若f(0)=0,2則C為f(X)=0的根；否則，若f(a)與f(c)異號(hào)，則令[a1,b]=[a,c];若f(b)與0°°1°°°f(q)異號(hào)，則令[a1,b1]=[C0,b0]。依此做下去，當(dāng)發(fā)現(xiàn)f(Cn)=0時(shí)或區(qū)間[a*,bn]足夠小，就認(rèn)為找到了方程的根。列舉法的定義：是蠻力策略的一種表現(xiàn)形式，它依照問(wèn)題中的條件將可能的情況一一列舉出來(lái)，逐一嘗試從中找出滿足問(wèn)題條件的解。蠻力法的典型模范：(P136)1)最小公倍數(shù)問(wèn)題；2)獄吏問(wèn)題。分治法的設(shè)計(jì)思想：將一個(gè)難以直接解決的大問(wèn)題，切割成一些規(guī)模較小的幾個(gè)相似問(wèn)題，以便分而治之，各個(gè)擊破。與遞歸算法相似。分治法的基本步驟：1)分解；2)解決；3)合并。大整數(shù)乘法問(wèn)題(P146)的算法解析：將兩個(gè)乘數(shù)及其積都按由低位到高位的序次，逐位儲(chǔ)藏到數(shù)組元素中。儲(chǔ)藏好兩個(gè)高精度數(shù)據(jù)后，模擬豎式乘法，讓兩個(gè)高精度數(shù)據(jù)的按位交織相乘，并漸漸累加，即可獲得精確的計(jì)算結(jié)果。用二重循環(huán)即可控制兩個(gè)數(shù)的各位數(shù)字按位交織相乘的過(guò)程。貪心算法的定義：優(yōu)選文檔優(yōu)選文檔又叫登山法，其根本思想是漸漸獲得最優(yōu)解，是解決最優(yōu)化問(wèn)題時(shí)的一種簡(jiǎn)單但適用范圍有限的策略?！柏澬摹笨梢岳斫鉃橐詽u漸的局部最優(yōu)，達(dá)到最后的全局最優(yōu)。埃及分?jǐn)?shù)問(wèn)題(P160)的算法解析：找最小的n,使分?jǐn)?shù)f>1/n;輸出1/n;計(jì)算f=f-1/n;若此時(shí)的f是埃及分?jǐn)?shù)，輸出f,否則返回第一步。貪心算法的基本思路：從問(wèn)題的某一個(gè)初始解出發(fā)漸漸逼近給定的目標(biāo)，每一步都作一個(gè)不可以回溯的決策，盡可能地求得最好的解。動(dòng)向規(guī)劃的基本思想：把求解的問(wèn)題分成好多階段或多個(gè)子問(wèn)題，爾后按序次求解各子問(wèn)題。前一子問(wèn)題的解，為后一子問(wèn)題的求解供應(yīng)了適用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，經(jīng)過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，扔掉其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。不同樣算法策略特點(diǎn)總結(jié)：1、貪心法：“經(jīng)過(guò)局部最優(yōu)獲得全局最優(yōu)”2、遞推法：由當(dāng)前問(wèn)題的漸漸解決從而獲得整個(gè)問(wèn)題的解，多用于計(jì)算。3、遞歸法：利用大問(wèn)題與其子問(wèn)題間的遞推關(guān)系來(lái)解決問(wèn)題。4、列舉法：逐一試一試問(wèn)題的所有可能的解，從而找出真切的解，多用于決策類問(wèn)題。5、遞歸回溯法：經(jīng)過(guò)遞歸試一試遍歷問(wèn)題各個(gè)可能解得的通路，當(dāng)發(fā)現(xiàn)此路不通時(shí)，回溯到上一步連續(xù)試一試其他通路。6、分治法：把一個(gè)大問(wèn)題分解成若干個(gè)簡(jiǎn)單解決的子問(wèn)題，分而治之，爾后把子問(wèn)題的解合成，獲得大問(wèn)題的解，多用于較復(fù)雜的問(wèn)題。7、動(dòng)向規(guī)劃法：經(jīng)過(guò)多階段決策過(guò)程來(lái)解決問(wèn)題。每個(gè)階段決策的結(jié)果是一個(gè)決策結(jié)果序列，這個(gè)結(jié)果序列的最優(yōu)結(jié)果，取決于今后每個(gè)階段的決策。搜尋算法的定義：有目的地列舉一個(gè)問(wèn)題的部分或所有的可能情況，從而找到問(wèn)題的解。顯示圖的常用方法：）毗鄰矩陣法：毗鄰矩陣是表示極點(diǎn)之間相鄰關(guān)系的矩陣。）毗鄰表法：對(duì)于圖G中的每個(gè)結(jié)點(diǎn)vi，該方法把所有毗鄰于vi的極點(diǎn)vj鏈成一個(gè)單鏈，這個(gè)單鏈表就稱為極點(diǎn)vi的毗鄰表。毗鄰表由極點(diǎn)表和邊表兩部分組成。廣度優(yōu)先搜尋算法的基本思路：經(jīng)過(guò)搜尋圖的過(guò)程中進(jìn)行相應(yīng)的操作，從而解決問(wèn)題，主要用于解決在顯式圖中搜尋某一方案的問(wèn)題。）毗鄰表表示圖的廣度優(yōu)先搜尋算法：intvisited[n];bfs（intk,graphhead[]）{intI;queueQ;優(yōu)選文檔優(yōu)選文檔edgenode*p;InitQueue(Q);print(“visitvertex”,k);visited[k]=1;EnQueue(Q,k);while(notQueueEmpty(Q)){i=DeQueue(Q);p=head[i].firstedge;while(p<>null){if(visited[p->adjvex]=0){print(“visitertex”,p->adjvex);visited[p->adjvex]=1;EnQueue(Q,p->adjvex);}p=p->next;}}}2)毗鄰矩陣表示的圖的廣度優(yōu)先搜尋算法：brsm(intk,graphg[][100],intn){inti,j;queueQ;InitQueue(Q);print(“visitvertex”,k);visited[k]=1;EnQueue(Q,k);while(notQueueEmpty(Q)){i=DeQueue(Q);for(j=0;j<n;j++)if(g[i][j]=1andvisited[j]=0){print(“visitvertex”,j);visited[j]=1;EnQueue(Q,j);}}}選路徑問(wèn)題(P198)的算法解析：運(yùn)用廣度優(yōu)先搜尋，逐層搜尋正好可以趕忙找到一個(gè)結(jié)點(diǎn)與另一個(gè)結(jié)點(diǎn)相對(duì)而言最直接的路徑。走迷宮問(wèn)題(P200)的算法解析：運(yùn)用廣度優(yōu)先搜尋，從入口開始廣度優(yōu)先搜尋所有可到達(dá)的方格入隊(duì)，再擴(kuò)展隊(duì)首的方格，直到搜尋到出口時(shí)算法結(jié)束。優(yōu)選文檔優(yōu)選文檔深度優(yōu)先搜尋算法的基本思路：深度優(yōu)先搜尋和廣度優(yōu)先搜尋的基本思路同樣。由于深度優(yōu)先搜尋的E結(jié)點(diǎn)是分多次進(jìn)行擴(kuò)展的，所以它可以搜尋到問(wèn)題所有可能的解決方案。)用毗鄰表儲(chǔ)藏圖的搜尋算法以下：intvisited[n];graphhead[100];dfs(intk){edgenode*ptr;visited[k]=1;print(“接見”,k);ptr=head[k].firstedge;while(ptr<>null){if(visited[ptr->vertex]=0)dfs(ptr->vertex)ptr=ptr->nextnode;}})用毗鄰矩陣儲(chǔ)藏圖的搜尋算法以下：intvisited[n];graphg[][100],intn;dfsm(intk){intj;print(“接見”,k);visited[k]=1;for(j=1;j<=n;j++)if(g[k][j]=1andvisited[j]=0)dfsm(g,j);}走迷宮問(wèn)題(P204)的算法解析：深度優(yōu)先搜尋，就是素來(lái)向著可通行的下一個(gè)方格進(jìn)行，直到搜尋到出口就找到一個(gè)解。若行不通，則返回上一個(gè)方格，連續(xù)搜尋其他方向。七巧板問(wèn)題(P206)的算法解析：在深度優(yōu)先搜尋極點(diǎn)時(shí)，其實(shí)不加入任何涂色的策略，可是對(duì)每一個(gè)極點(diǎn)逐一試一試4種顏色，檢查當(dāng)前頂優(yōu)選文檔優(yōu)選文檔點(diǎn)的顏色可否與前面已確定的相鄰極點(diǎn)的顏色發(fā)生矛盾，若不矛盾，則連續(xù)以同樣的方法辦理