算法設(shè)計(jì)與分析 課件 第一章 緒論

計(jì)算機(jī)算法設(shè)計(jì)與分析第1章概述例1.1求兩個(gè)正整數(shù)的最大公約數(shù)方法一：利用質(zhì)因數(shù)分解法求解最大公約數(shù)，其具體步驟描述如下：（1）輸入兩個(gè)正整數(shù)a和b。（2）將a和b分別進(jìn)行質(zhì)因數(shù)分解，得到它們的所有質(zhì)因數(shù)的乘積形式。（3）將a和b中相同的所有質(zhì)因數(shù)乘積計(jì)算出來(lái)，得到的結(jié)果即為a和b的最大公約數(shù)。若a或b無(wú)質(zhì)因數(shù)（除1和該數(shù)本身外），則最大公約數(shù)為1。例1.1求任意兩個(gè)正整數(shù)的最大公約數(shù)以具體計(jì)算為例，假設(shè)需要求解的兩個(gè)整數(shù)為42和28，42=2×3×7，28=2×2×7共同的質(zhì)因數(shù)2和7，因此，42和28的最大公約數(shù)為2×7=14利用方法一可以快速求出兩個(gè)整數(shù)的最大公約數(shù)，但方法一的描述過(guò)程不能稱為一個(gè)正真意義上的算法，因?yàn)榈?2)步?jīng)]有明確如何將正整數(shù)a和b進(jìn)行質(zhì)因數(shù)分解，且質(zhì)因數(shù)分解是一個(gè)NP類問(wèn)題，目前尚未找到有效的解決方法。第(3)步也沒(méi)有明確定義在兩個(gè)質(zhì)因數(shù)序列中如何找到相同的質(zhì)因數(shù)元素。因此方法一描述不滿足算法的確定性和可行性。例1.1求任意兩個(gè)正整數(shù)的最大公約數(shù)方法二：利用蠻力窮舉法求解最大公約數(shù)，具體步驟描述如下：（1）輸入a和b。（2）將a和b中的較小者賦值給r。（3）若a、b除以r的余數(shù)同時(shí)等于0，轉(zhuǎn)（5），否則往下執(zhí)行（4）。（4）執(zhí)行r=r-1，轉(zhuǎn)（3）。（5）輸出r，執(zhí)行結(jié)束。主要思想：是從兩個(gè)整數(shù)中較小者開(kāi)始，去逐步尋找能被兩整數(shù)同時(shí)整除的數(shù)，一旦發(fā)現(xiàn)則終止尋找，并將該數(shù)作為兩整數(shù)的最大公約數(shù)。例1.1求任意兩個(gè)正整數(shù)的最大公約數(shù)r=2842%28=14,28%28=0,r=28-1=2742%27=15,28%27=1,r=27-1=2642%26=16,28%26=2,r=26-1=2542%25=17,28%25=3,r=25-1=2442%24=18,28%24=4,r=24-1=2342%23=19,28%23=5,r=23-1=2242%22=20,28%22=6,r=22-1=2142%21=0,28%21=7,r=21-1=2042%20=2,28%20=8,r=20-1=1942%19=4,28%19=9,r=19-1=1842%18=6,28%18=10,r=18-1=1742%17=8,28%17=11,r=17-1=1642%16=10,28%16=12,r=16-1=1542%15=12,28%15=13,r=15-1=1442%14=0,28%14=0輸出r，結(jié)果為14。以具體計(jì)算為例，設(shè)a=42和b=28，則計(jì)算過(guò)程為：例1.1求任意兩個(gè)正整數(shù)的最大公約數(shù)在a=42，b=28的情況下，窮舉法運(yùn)行了15步才計(jì)算出結(jié)果。方法二窮舉法非常簡(jiǎn)單，計(jì)算過(guò)程易于理解，但窮舉法的效率非常低。例1.1求任意兩個(gè)正整數(shù)的最大公約數(shù)方法三：利用輾轉(zhuǎn)相除法（也稱歐幾里得算法）求解最大公約數(shù)，具體步驟描述如下：（1）輸入兩個(gè)整數(shù)a和b。（2）若a<b則將a，b的值互換，以保持a是兩個(gè)整數(shù)中較大者，b為較小者。（3）將a除以b的余數(shù)賦值給r，若余數(shù)r等于0，則執(zhí)行（5），否則往下執(zhí)行（4）（4）將除數(shù)b賦值給a，將余數(shù)r賦值給b，轉(zhuǎn)（3）重復(fù)執(zhí)行（5）b為所求最大公約數(shù)，輸出b，執(zhí)行結(jié)束。例1.1求任意兩個(gè)正整數(shù)的最大公約數(shù)以具體計(jì)算為例，設(shè)a=42和b=28，則計(jì)算過(guò)程為：r=42%28=14,a=28,b=14r=28%14=0輸出b，結(jié)果為14。在a=42，b=28的情況下，輾轉(zhuǎn)相除法只運(yùn)行了2步就計(jì)算出結(jié)果。例1.1求任意兩個(gè)正整數(shù)的最大公約數(shù)算法：輾轉(zhuǎn)相除法;輸入：兩個(gè)正整數(shù)a,b;

輸出：最大公約數(shù)Max_common_divisor(a,b)beginifa<bthena與b互換endramodbwhiler≠0doab,br,ramodbendprintbend計(jì)算機(jī)算法設(shè)計(jì)與分析第一章緒論一個(gè)快遞小哥從快遞中心點(diǎn)出發(fā)，到周邊四個(gè)小區(qū)送快遞，要求經(jīng)過(guò)每個(gè)小區(qū)且只能每個(gè)小區(qū)僅經(jīng)過(guò)一次，最后回到快遞中心點(diǎn)。問(wèn)快遞小哥應(yīng)如何安排派送路線較好？例1.3快遞員路線安排問(wèn)題起

終ABCDEA03456B30265C42043D56405E65350（1）問(wèn)題分析與問(wèn)題抽象，這是一個(gè)典型的TSP問(wèn)題將小區(qū)抽象為下圖的頂點(diǎn)，兩個(gè)小區(qū)之間有路直達(dá)，則對(duì)應(yīng)的兩個(gè)頂點(diǎn)之間有邊關(guān)聯(lián)，邊的權(quán)值為兩個(gè)小區(qū)之間的距離。則將快遞員路線安排問(wèn)題抽象為從頂點(diǎn)A(設(shè)A為快遞中心)出發(fā)經(jīng)過(guò)圖中其余頂點(diǎn)后回到頂點(diǎn)A的最短簡(jiǎn)單回路問(wèn)題。例1.3快遞員路線安排問(wèn)題3365456542EBDCA（2）數(shù)學(xué)建模：例1.3快遞員路線安排問(wèn)題3365456542EBDCA（3）方法一蠻力法：列出每一條可供選擇的路線，計(jì)算出每條路線的距離長(zhǎng)度，最后從中選擇出一條最短路線。最短路程為：A-->B-->C-->E-->D-->A或者A-->D-->E-->C-->B-->A，最短路徑長(zhǎng)度為:18。例1.3快遞員路線安排問(wèn)題3365456542EBDCA（3）蠻力法算法效率分析：使用蠻力法列舉除出發(fā)小區(qū)外所有小區(qū)的排列，然后選取路徑最短的路線。n-1個(gè)小區(qū)的排列數(shù)為(n-1)!，當(dāng)n=20時(shí)，遍歷路線總數(shù)約為1.216×1017，計(jì)算機(jī)以每秒1000萬(wàn)條路線的檢索速度計(jì)算，則約需要386年才能完成。故蠻力法的時(shí)間復(fù)雜度太高，當(dāng)頂點(diǎn)數(shù)過(guò)多時(shí)并不適用。例1.3快遞員路線安排問(wèn)題（3）方法二貪心法：每次在選擇下一個(gè)小區(qū)時(shí)，只考慮當(dāng)前情況。在沒(méi)有經(jīng)過(guò)的小區(qū)中，選擇距離當(dāng)前小區(qū)最近的一個(gè)，直到經(jīng)過(guò)所有小區(qū)，最后回到快遞中心。A例1.3快遞員路線安排問(wèn)題3365456542EBDCA貪心法的優(yōu)點(diǎn)是效率很高，只要n-1步判斷就能得到結(jié)果。但缺點(diǎn)是不一定能找到問(wèn)題的最優(yōu)解。算法：貪心法—偽代碼描述輸入：小區(qū)數(shù)量n，鄰接矩陣e[i,j]，頂點(diǎn)v[i]，出發(fā)小區(qū)編號(hào)go_city，index當(dāng)前小區(qū)編號(hào)。輸出：最短路線上的頂點(diǎn)信息，最短路徑長(zhǎng)度min_l。Greedy(index):beginfori

1tondo ifi不是出發(fā)頂點(diǎn)go_citythen forj

1tondo if沒(méi)有經(jīng)過(guò)小區(qū)jthen

篩選與當(dāng)前出發(fā)點(diǎn)最短的頂點(diǎn)，并標(biāo)記為cur_j endifendfor min_l

min_l+e[index,cur_j] index

cur_j//從出發(fā)點(diǎn)cur_j，繼續(xù)下一步求解

并置cur_j頂點(diǎn)為經(jīng)過(guò)標(biāo)記

endifend for

min_lmin_l+e[index,go_city]//加上最后一個(gè)小區(qū)到go_city小區(qū)的距離end例1.3快遞員路線安排問(wèn)題計(jì)算機(jī)算法設(shè)計(jì)與分析第一章概述1.4.1算法的效率分析目的評(píng)估算法體現(xiàn)算法運(yùn)行時(shí)所需要消耗的計(jì)算機(jī)資源占用CPU的計(jì)算時(shí)間量稱為時(shí)間復(fù)雜度占用內(nèi)存的存儲(chǔ)空間量稱為空間復(fù)雜度算法復(fù)雜度分析一般采用事前分析方式而是不事后統(tǒng)計(jì)法算法的效率分析算法的時(shí)間復(fù)雜度T和空間復(fù)雜度S的函數(shù)：T=T(N,I)S=S(N,I)N表示問(wèn)題規(guī)模，I表示算法輸入在實(shí)際應(yīng)用中，關(guān)注時(shí)間效率多于空間效率。算法時(shí)間復(fù)雜度分析評(píng)估算法時(shí)間復(fù)雜度，應(yīng)盡量做到客觀反映算法的本質(zhì)特征和屬性。所以，算法時(shí)間復(fù)雜度分析應(yīng)該要有一個(gè)不依賴于計(jì)算機(jī)硬件配置、問(wèn)題規(guī)模和輸入實(shí)例的抽象表示。算法時(shí)間復(fù)雜度分析假設(shè)在一臺(tái)抽象的計(jì)算機(jī)上提供了k種元運(yùn)算O1，O2，…，Ok，每個(gè)元運(yùn)算執(zhí)行的時(shí)間分別為t1，t2，...，tk。元運(yùn)算通常指的是算法中最基本的操作步驟，一個(gè)元運(yùn)算可以是基本的算術(shù)運(yùn)算（如加法、減法、乘法、除法）、比較操作、賦值操作、數(shù)組訪問(wèn)或迭代循環(huán)等。算法時(shí)間復(fù)雜度分析T(N，I)表示算法在這臺(tái)抽象計(jì)算機(jī)上運(yùn)行所需要的的時(shí)間，設(shè)，在算法中

元運(yùn)算Oi被調(diào)用的次數(shù)為ei，ei=ei(N,I)，因此，T(N,I)一般化的表示：算法時(shí)間復(fù)雜度分析為消除公式中ti表示的元運(yùn)算執(zhí)行的具體時(shí)間，不妨假設(shè)所有的元運(yùn)算都在一個(gè)單位時(shí)間內(nèi)完成或者將ti抽象表示為一條執(zhí)行語(yǔ)句或表達(dá)式所用時(shí)間，則計(jì)算T(N,I)的工作就變?yōu)榻y(tǒng)計(jì)計(jì)算語(yǔ)句的頻度，從而簡(jiǎn)化復(fù)雜度的求解。例1.4插入排序問(wèn)題時(shí)間復(fù)雜度計(jì)算

算法：插入排序（升序排序）

輸入：數(shù)組元素array，元素個(gè)數(shù)n

輸出：升序的數(shù)組元素array

InsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移動(dòng)元素6 j

j–17 end8 array[j+1]

key9

endend當(dāng)輸入數(shù)據(jù)為1,2,3,4,5時(shí)，語(yǔ)句2、3、8被執(zhí)行4次，語(yǔ)句5、6被執(zhí)行0次。當(dāng)輸入數(shù)據(jù)為5,4,3,2,1時(shí)，語(yǔ)句2、3、8被執(zhí)行4次，語(yǔ)句5、6被執(zhí)行10次。算法時(shí)間復(fù)雜度分析對(duì)同一個(gè)算法，運(yùn)行不同的輸入實(shí)例時(shí)，算法語(yǔ)句執(zhí)行的次數(shù)差異明顯。實(shí)際上，在統(tǒng)計(jì)時(shí)間復(fù)雜度時(shí)，我們不可能對(duì)規(guī)模N的每一種合法輸入都去統(tǒng)計(jì)各個(gè)算法語(yǔ)句執(zhí)行的次數(shù)，這時(shí)就需要對(duì)輸入實(shí)例做一個(gè)合理簡(jiǎn)化，即將輸入實(shí)例進(jìn)行特化。算法時(shí)間復(fù)雜度分析（1）最壞情況下的時(shí)間復(fù)雜度：IN是規(guī)模為N的合法輸入集合，I*是IN中使T(N,I)達(dá)到Tmax(N)的合法輸入。最壞情況下的時(shí)間復(fù)雜度就是將所有的合法輸入實(shí)例中最壞的那個(gè)輸入實(shí)例I*找出來(lái)，統(tǒng)計(jì)在輸入實(shí)例I*時(shí)算法語(yǔ)句執(zhí)行的次數(shù)來(lái)評(píng)估算法時(shí)間復(fù)雜度。算法時(shí)間復(fù)雜度分析（2）最好情況下的時(shí)間復(fù)雜度：I'是IN中使T(N,I)達(dá)到Tmin(N)的合法輸入，將所有的合法輸入實(shí)例中最好的那個(gè)輸入實(shí)例I'找出來(lái)，統(tǒng)計(jì)在輸入實(shí)例I'時(shí)算法語(yǔ)句執(zhí)行的次數(shù)來(lái)評(píng)估算法時(shí)間復(fù)雜度。算法時(shí)間復(fù)雜度分析（3）平均情況下的時(shí)間復(fù)雜度：P(I)是算法應(yīng)用中出現(xiàn)輸入實(shí)例I的概率，全部合法輸入實(shí)例的概率總和為1。平均時(shí)間復(fù)雜度是用每一個(gè)輸入實(shí)例出現(xiàn)的概率，計(jì)算其數(shù)學(xué)期望。在分析算法時(shí)間復(fù)雜度的時(shí)候，往往關(guān)注的是最壞情況下算法的時(shí)間復(fù)雜度。例1.4插入排序問(wèn)題時(shí)間復(fù)雜度計(jì)算

算法：插入排序（升序排序）

輸入：數(shù)組元素array，元素個(gè)數(shù)n

輸出：升序的數(shù)組元素array

InsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移動(dòng)元素6 j

j–17 end8 array[j+1]

key9

endend語(yǔ)句2,3,8分別執(zhí)行N-1次語(yǔ)句5,6執(zhí)行的次數(shù)分為1,2,3，...，N-1次算法時(shí)間復(fù)雜度分析語(yǔ)句2,3,8分別執(zhí)行N-1次，語(yǔ)句5,6執(zhí)行的次數(shù)分為1,2,3，...，N-1次，所以：當(dāng)N比較大時(shí)，N2/2為主要因素，后面項(xiàng)為次要因素忽略次要因素，簡(jiǎn)化時(shí)間復(fù)雜度函數(shù)的表示。計(jì)算機(jī)算法設(shè)計(jì)與分析第一章概述漸近時(shí)間復(fù)雜度分析設(shè)T(N)是算法A的時(shí)間復(fù)雜度函數(shù)，N是問(wèn)題規(guī)模，N≥0，且N∈Z。當(dāng)N

∞時(shí)，T(N)

∞。對(duì)于T(N)，如果存在T'(N)，使得當(dāng)N

∞時(shí)有那么，我們就說(shuō)T'(N)是算法A當(dāng)N

∞的漸近復(fù)雜度。漸近時(shí)間復(fù)雜度分析在漸近復(fù)雜度函數(shù)T'(N)中，階與T'(N)中的常數(shù)因子沒(méi)有關(guān)系，所以T'(N)可進(jìn)一步簡(jiǎn)化，省略常數(shù)因子。例1.4中的T'(N)可取值N2即可。需要注意的是，函數(shù)簡(jiǎn)化并不是一種精確計(jì)算復(fù)雜度的方法，而是一種近似評(píng)估的方式。例1.4中的T'(N)=N2/2+5N/2-3漸近時(shí)間復(fù)雜度分析定義1.1設(shè)f(N)和g(N)是正整數(shù)集上的函數(shù)。如果?c≥0和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有0≤f(N)≤cg(N)，則稱函數(shù)f(N)充分大時(shí)上有界，g(N)是f(N)的一個(gè)上界，記為f(N)=O(g(N))，即f(N)的階不高于g(N)的階，如圖所示。不是直接比較f(N)和g(N)的數(shù)值大小，O表示的只是一個(gè)充分大的上界，上界的階越低則算法時(shí)間復(fù)雜度的評(píng)估越精確，結(jié)果值越有價(jià)值N0cg(N)f(N)漸近時(shí)間復(fù)雜度分析例1.5求5n+4，n2+nlogn，2n+n2，10000的上界。n≥4時(shí)，5n+4≤6n，則5n+4=O(n)n≥1時(shí)，n2+nlogn≤2n2，則n2+nlogn=O(n2)n≥1時(shí)，2n+n2≤2*2n，則2n+n2=O(2n)對(duì)于常整數(shù)10000，算法執(zhí)行時(shí)間與問(wèn)題規(guī)模無(wú)關(guān)，無(wú)論問(wèn)題規(guī)模多大，算法都在固定時(shí)間內(nèi)完成。因此無(wú)論是10000還是其他任何常數(shù)輸入，它的時(shí)間復(fù)雜度是一個(gè)常數(shù)級(jí)別的復(fù)雜度，即O(1)。漸近時(shí)間復(fù)雜度分析例1.6給定多項(xiàng)式函數(shù)：

試證明T(n)=O(nm)。證明：設(shè)n0=1,對(duì)于任意的n，若n≥n0=1，則：存在c≥0和自然數(shù)n0=1，使得當(dāng)n≥n0時(shí)有T(n)≤cnm，故T(n)=O(nm)成立。漸近時(shí)間復(fù)雜度分析根據(jù)定義1.1，我們有如下O(n)的性質(zhì)：（1）O(f)+O(g)=O(max(f,g))；算法最復(fù)雜的部分運(yùn)行時(shí)間就是算法的時(shí)間復(fù)雜度。（2）O(f)+O(g)=O(f+g)；算法中并行語(yǔ)句的時(shí)間復(fù)雜度等于各個(gè)語(yǔ)句運(yùn)行時(shí)間之和。（3）O(f)×O(g)=O(f×g)；循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體運(yùn)行時(shí)間與循環(huán)次數(shù)的乘積。（4）O(cf(n))=O(f(n))，c∈Z+；算法的時(shí)間復(fù)雜度是運(yùn)行時(shí)間函數(shù)的數(shù)量級(jí)。（5）如果g(n)=O(f(n))，則O(f)+O(g)=O(f)；算法的時(shí)間復(fù)雜度是運(yùn)行時(shí)間函數(shù)的最高階。（6）f=O(f)。漸近時(shí)間復(fù)雜度分析定義1.2設(shè)f(N)和g(N)是正整數(shù)集上的函數(shù)。如果?c≥0和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)≥cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)下有界，且g(N)是f(N)的一個(gè)下界，記為f(N)=Ω(g(N))，即f(N)的階不低于g(N)的階，如圖所示。N0cg(N)f(N)漸近時(shí)間復(fù)雜度分析例1.8求5n+1，n2+nlogn的下界。當(dāng)n≥1時(shí)，5n+1≥5n，則5n+1=Ω(n)當(dāng)n≥1時(shí)，n2+nlogn≥n2，則n2+

nlogn

=Ω(n2)；n2+

nlogn

≥nlogn，則n2+

nlogn

=Ω(nlogn)，但nlogn≠Ω(n2)。根據(jù)定義1.2可知，n2+nlogn=Ω(n2)和n2+

nlogn

=Ω(nlogn)都成立，算法時(shí)間復(fù)雜度一般取最大下界。下界的階越高，評(píng)估越精確，結(jié)果越有價(jià)值，Ω通常也表示求解問(wèn)題的最好情況下的時(shí)間復(fù)雜度。漸近時(shí)間復(fù)雜度分析定義1.3設(shè)f(N)和g(N)是正整數(shù)集上的函數(shù)。如果?c1≥0、?c2≥0和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有0≤c1g(N)≤f(N)≤c2g(N)，則稱g(N)是f(N)的緊確界。記為f(N)=θ(g(N))，如圖1.7所示。若f(N)=θ(g(N))，則當(dāng)且僅當(dāng)f(n)=O(g(N))且f(N)=Ω(g(N))，也稱g(N)和f(N)同階。N0c1g(N)f(N)c2g(N)漸近時(shí)間復(fù)雜度分析例1.9

求n2+nlogn的緊確界。由例1.5和例1.8可知：n2+nlogn=O(n2)，n2+nlogn=Ω(n2)，因此n2+nlogn=θ(n2)。計(jì)算機(jī)算法設(shè)計(jì)與分析第一章概述非遞歸算法的時(shí)間復(fù)雜度分析在分析非遞歸算法時(shí)，主要遵循如下步驟：（1）確定核心操作：比如算法中的賦值、比較、算術(shù)運(yùn)算、邏輯運(yùn)算、變量輸入輸出等操作，一般稱為基本操作。也可以將內(nèi)層循環(huán)的若干個(gè)基本操作構(gòu)成的程序塊整體看成一個(gè)稍大一點(diǎn)的基本操作。（2）計(jì)算核心操作總的執(zhí)行次數(shù)：計(jì)算核心基本操作的執(zhí)行次數(shù)，一般是多項(xiàng)式和的形式。（3）求解其漸近解：對(duì)核心操作總執(zhí)行次數(shù)表達(dá)式進(jìn)行計(jì)算化簡(jiǎn)，并用O(?)形式表示。非遞歸算法的時(shí)間復(fù)雜度分析例1.10查找元素t在數(shù)組a中第一次出現(xiàn)的位置，若查找失敗返回-1。分析順序查找算法時(shí)間復(fù)雜度。本算法描述中的核心操作是語(yǔ)句3，最好的情況下，時(shí)間復(fù)雜度T(n)=O(1)。最壞的情況是整個(gè)循環(huán)語(yǔ)句1執(zhí)行完畢，即語(yǔ)句3被執(zhí)行n次而結(jié)束，此時(shí)T(n)=O(n)非遞歸算法的時(shí)間復(fù)雜度分析例1.11查找元素t在升序數(shù)組a中第一次出現(xiàn)的位置，若查找失敗返回-1。分析二分查找算法時(shí)間復(fù)雜度。非遞歸算法的時(shí)間復(fù)雜度分析核心操作是語(yǔ)句3~6，最好的情況下，執(zhí)行到語(yǔ)句4直接結(jié)束，時(shí)間復(fù)雜度T(n)=O(1)。最壞情況是每次進(jìn)入while循環(huán)，搜索范圍a[left]~a[right]