湘潭大學(xué)算法設(shè)計與分析知識點

1、第一章算法概述1、算法的五個性質(zhì)：有窮性、確定性、能行性、輸入、輸出。2、算法的復(fù)雜性取決于：(1)求解問題的規(guī)模(n) , (2)具體的輸入數(shù)據(jù)(i), (3)算法 本身的設(shè)計(a), c=f(n/i/a)o3、算法的時間復(fù)雜度的上界，下界，同階，低階的表示。4、常用算法的設(shè)計技術(shù)：分治法、動態(tài)規(guī)劃法、貪心法、冋溯法和分支界限法。5、常用的幾種數(shù)據(jù)結(jié)構(gòu)：線性表、樹、圖。第二章遞歸與分治1、遞歸算法的思想:將對較大規(guī)模的對彖的操作歸結(jié)為對較小規(guī)模的對象實施同樣的操作。 遞歸的時間復(fù)雜性可歸結(jié)為遞歸方程：tin) <in = 1at(n b) + d(n) n> 1其中，a是子問題的

2、個數(shù)，b是遞減的步長，表示遞減方式，d(n)是合成子問題的開銷。遞歸元的遞減方式有兩種：1、減法，即n-b,的形式。2、除法，即n/b,的形式。2、d(n)為常數(shù) c：這時,t(n) = 0(np)od(n)為線形函數(shù)cn：當(dāng)a v btl寸當(dāng)玄=bh寸當(dāng)a a匕時當(dāng)a v d(b)時 當(dāng)a = d(b)時 當(dāng)a > d(b)時r o(n)t(n) =i o(nlogbn) i o(np) 其中，p = log baod(n)為幕函數(shù)nx：r o(nx)t(n) = j 0(nplogbn)i o(np)其中，p = logbao考慮下列遞歸方程：t(l) = 1(1) t(n) = 4

3、t(n/2)+ n(2) t(n) = 4t(n/2) +n2(3) t(n) = 4t(n/2) +n3解：方程中均為a = 4, b = 2,其齊次解為對, a>b1(d(n) = n) .i t(n)=o(n2)；對，i a = b2 (d(n) = n2)t(n) = o(n2log n)；對，v a<b3(d(n) = n3)t(n) = o(n3)；證明一個算法的正確性需要證明兩點：1、算法的部分正確性。2、算法的終止性。第三章貪心算法(旅行商問題、單源最短路徑問題)以下兩種算法都是為了查找最有樹問題的算法：1、prim算法的基本思想：在保證連通的前提下依次選出權(quán)重較小

4、的n-1條邊。2、kruskal算法的基本思想：基本思想：在保證無冋路的前提下依次選出權(quán)重較小的n - 1 條邊。3、prim與kruskal兩算法的復(fù)雜性：prim算法為兩重循壞，外層循壞為n次，內(nèi)層循壞為0(n),因此其復(fù)雜性為0()。kruskal算法屮，設(shè)邊數(shù)為e,則邊排序的時間為0(eloge),最多對e條邊各掃描一次，每 次確定邊的時間為o(loge),所以整個時間復(fù)雜性為o(eloge)。當(dāng)e = q(n2)時,kruskal算法要比prim算法差;當(dāng)e二o()時，kruskal算法比prim算法好得多。4、貪心算法的基本要素是：貪心選擇性質(zhì)。5、最小生成樹問題、單源最短路徑問題

5、、旅行商問題、01背包問題，貪心算法不能夠找 到最優(yōu)解。6、活動安排問題、最優(yōu)裝載問題，貪心算法可以找到最優(yōu)解。第四章動態(tài)規(guī)劃1、最短路徑問題的計算方法。(p44例題)2、最有子結(jié)構(gòu)的性質(zhì)：最優(yōu)解的子結(jié)構(gòu)也是最優(yōu)的。3、動態(tài)規(guī)劃的基本要素：(1)最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解是由其子問題的最優(yōu)解所構(gòu)成的。(2)重疊子問題：子問題之間并非相互獨立的，而是彼此有重疊的。4、動態(tài)規(guī)劃算法的步驟：1.找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特性。2.遞歸地定義最優(yōu)解。3.以自底向上的方式計算出各子結(jié)構(gòu)的最優(yōu)值，并流入表格中保 存。4.根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。5、在有n個頂點的凸多邊形的三角剖分中，恰有

6、n3條眩，n2個三角形。第五章回溯法1、三種搜索方法：(1)廣度優(yōu)先搜索的優(yōu)點是一定能找到解；缺點是空間復(fù)雜性和時間復(fù) 雜性都大。(2)深度優(yōu)先搜索的優(yōu)點是空間復(fù)雜性和時間復(fù)雜性較小；缺點是不一定能找到 解。(3)啟發(fā)式搜索是最好優(yōu)先的搜索，優(yōu)點是一般來說能較快地找到解，即其吋間復(fù)雜性 更小；缺點是需要設(shè)計一個評價函數(shù)，并且評價函數(shù)的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣。2、回溯法是一種通用的算法，實為深度優(yōu)先的搜索方法?；厮莘梢赃f歸實現(xiàn)，也可以迭代實現(xiàn)?；厮莘ㄍǔＧ蠼馊悊栴}：求排列：時間復(fù)雜性為0(f(n)n!)；(2) 求子集：時間復(fù)雜性為0(f(n)2n)；(3) 求路徑：時間復(fù)雜性為0(f(

7、n)kn)o這里f(n)為處理一個結(jié)點的時間復(fù)雜性。第六章分支界限法1、分支界限法德兩個要點：(1)評價函數(shù)的構(gòu)造。(2)搜索路徑的構(gòu)造。2、所謂分支限界法就是通過評價函數(shù)及其上下界兩數(shù)的計算，將狀態(tài)空間中不可能產(chǎn)生最 佳解的子樹剪去，減少搜索的范i韋i，提高效率。因而更準(zhǔn)確的稱呼應(yīng)是“界限剪支法”分支限界法求tsp的搜索廠8 2540 31 275 oo17 30 2519 15oo 6 19 5024 oo 622 87 10 oo0322386337r rdo°24795345233找到了第一條周游路線1- 5 - 3 - 42 -1, 長度為95。這不是最短周游路線，49需要

8、修改上界后繼續(xù)搜索。第七章字符串1、幾個名詞的定義：串的長度，子串，位置，串相等，模式匹配。2、kmp算法：next函數(shù)的計算，newnext函數(shù)的計算。3、bm算法：dist函數(shù)的計算。4、kr算法：指印函數(shù)的要求：(1)速度快。(2)沖突概率小o (3)相鄰兩個字符串的hash 值必須有相關(guān)性。5、kr算法的基本思想：首先計算模式串和正文串所有長度為m的子串的指印函數(shù)；然后 匹配與模式串指印函數(shù)相等的正文串中的子串，找到匹配串。6、kmp算法，bm算法，kr算法的優(yōu)缺點：三者中kmp算法的最壞情形下的時間復(fù)雜度 最低，而平均情形則三者差不多。kmp算法最早提出，應(yīng)用也最廣泛，而且它的優(yōu)勢在

9、于 無需對正文回溯，當(dāng)正文不能一次性讀入內(nèi)存時，這種優(yōu)勢是顯而易見的。bm算法的平均 性能也很出色，但它需要對正文進(jìn)行回溯，所以當(dāng)正文不能一次性讀入內(nèi)存時，可能會出現(xiàn)“抖動”，需要用雙緩沖區(qū)技術(shù)來處理這一問題。kr算法的優(yōu)勢在于可以推廣到二維模型, 而且可以并行地處理，所以較多地運用于圖形圖像領(lǐng)域。第九章概率算法1偽隨機數(shù)的產(chǎn)生方法：(1)線性同余法：實現(xiàn)簡單，速度快，具有較好的統(tǒng)計性能，廣 泛應(yīng)用于仿真，但不能用于加密。(2)線性反饋移位寄存器。2、舍伍德算法：(1)舍伍德算法總能求得問題的一個解，且所求得解的結(jié)果總是正確的。 其主要目的是消除算法所需計算時間對輸入實例的依賴。(2)當(dāng)一個確

10、定型算法最壞 情況下的計算復(fù)雜性與其平均情形下的復(fù)雜度有較大差別時，可以在這個確定型算法小 引入隨機性將它改造成一個舍伍徳算法，消除或減少問題的好壞實例間的這種差別。(3) 舍伍徳算法的精髓不是避免算法的最壞情況行為，而是設(shè)法消除這種最壞情形行為與特 定實例之間的關(guān)聯(lián)性。3、拉斯維加斯算法：(1)顯著地改進(jìn)算法的有效性，其至對某些迄今為止找不到有效算法 的問題，也能找到滿意的算法；但它所做的隨機性決策有可能導(dǎo)致算法找不到需要的解。(4)由于后者的原因，通常用boolean型方法表示拉斯維加斯型算法。4、蒙特卡洛算法：(1)蒙特卡羅算法用于求解問題的準(zhǔn)確解。(2)蒙特卡羅算法能求得一 個解，但未

11、必是正確的。其求得正確解的概率依賴于算法所用的時間。所用時間越多，得到 止確解的概率就越高，但它的缺點也在于此。在一般情況下，無法有效地判定所得到的解是 否肯定正確。第十章數(shù)據(jù)壓縮算法1、被壓縮的對象：物理空間，即數(shù)據(jù)存儲介質(zhì)的尺寸。時間區(qū)間，傳輸消息集合所需要的 時間。電磁頻譜區(qū)域，如為傳輸消息的帶寬等。2、ascii碼壓縮方法是一種經(jīng)過兩級壓縮之后可以減少56.25%的存儲空間的算法，它z適 用于純數(shù)字。3、哈夫曼編碼：哈夫曼編碼的長度筆筒，它的基本理論基于下列定理：在變長編碼屮，若 各碼字長度嚴(yán)格按照所對應(yīng)的符號出現(xiàn)概率的大小逆序排列，則其平均長度最小。4、字典法：基本思想：構(gòu)造一個字典，將信息屮反復(fù)出現(xiàn)的字符串，登記為較短的字符串， 解碼時對這種字符串，通過查字典，轉(zhuǎn)換為原字符串o最原始的字典法是模式置換壓縮算法。5、字典法存在的幾個困擾