算法效率分析與分治法的應(yīng)用

1、算法效率與分治算法的應(yīng)用長(zhǎng)沙市一中曹利國(guó)算法效率的評(píng)價(jià) 算法的評(píng)估 有時(shí)求解同一個(gè)問(wèn)題常常有多種可用的算法，在一定的條件下當(dāng)然要選擇使用好的算法。用什么方法評(píng)估算法的好壞呢？通常使用算法復(fù)雜性這一概念來(lái)評(píng)估算法。 算法評(píng)價(jià) 算法執(zhí)行時(shí)間需通過(guò)依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來(lái)度量。而度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法： 事后統(tǒng)計(jì)的方法 事前分析估算的方法 算法評(píng)價(jià) 一個(gè)用高級(jí)程序語(yǔ)言編寫(xiě)的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：依據(jù)的算法選用何種策略；問(wèn)題的規(guī)模.例如求100以內(nèi)還是1000以內(nèi)的素?cái)?shù)；書(shū)寫(xiě)程序的語(yǔ)言.對(duì)于同一個(gè)算法,實(shí)現(xiàn)語(yǔ)言的級(jí)別越高,執(zhí)行效率就越低

2、；編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；機(jī)器執(zhí)行指令的速度。 算法評(píng)價(jià) 一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)三種）和原操作（指固有數(shù)據(jù)類(lèi)型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果。 為了便于比較同一問(wèn)題的不同算法，通常的做法是，從算法中選取一種對(duì)于所研究的問(wèn)題（或算法類(lèi)型）來(lái)說(shuō)是基本運(yùn)算的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。 算法評(píng)價(jià) 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間量度記作T（n）= O（f（n）它表示問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f（n）的增長(zhǎng)率相同，稱(chēng)作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。算法評(píng)價(jià) 例如：在

3、下列三個(gè)程序段中，x:=x+1for i:=1 to n do x:=x+1;for j:=1 to n do for k:=1 to n do x:=x+1含基本操作“x增1”的語(yǔ)句x:=x+1的頻度分別為1，n和 n2 ，則這三個(gè)程序段的時(shí)間復(fù)雜度分別為O（1），O（n），O（n2），分別稱(chēng)為常量階、線性階和平方階。 算法評(píng)價(jià) 算法還可能呈現(xiàn)的時(shí)間復(fù)雜度有：對(duì)數(shù)階O（log n），指數(shù)階O（2n）等。在n很大時(shí), 不同數(shù)量級(jí)時(shí)間復(fù)雜度顯然有O（1）O（log n）O（n）O（nlog n）O（n2） O（n3）O（2n），可以看出，在算法設(shè)計(jì)時(shí)，我們應(yīng)該盡可能選用多項(xiàng)式階O(nk)的算法，

4、而不希望用指數(shù)階的算法。 算法評(píng)價(jià) 由于算法的時(shí)間復(fù)雜度考慮的只是對(duì)于問(wèn)題規(guī)模n的增長(zhǎng)率，則在難以計(jì)算基本操作執(zhí)行次數(shù)(或語(yǔ)句頻度)的情況下，只需求出它關(guān)于n的增長(zhǎng)率或階即可。例如，在下列程序段中：for i:=2 to n do for j:=2 to i-1 do x:=x+1語(yǔ)句x:=x+1執(zhí)行次數(shù)關(guān)于n的增長(zhǎng)率為n2，它是語(yǔ)句頻度表達(dá)式(n-1)(n-2)/2中增長(zhǎng)最快的一項(xiàng)。 算法評(píng)價(jià) 類(lèi)似于算法的時(shí)間復(fù)雜度，以空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作S(n)=O(f(n) 其中n為問(wèn)題的規(guī)模(或大小)。一個(gè)上機(jī)執(zhí)行的程序除了需要存儲(chǔ)空間來(lái)寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，

5、也需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。 算法評(píng)價(jià) 評(píng)價(jià)一個(gè)數(shù)學(xué)模型有以下幾個(gè)原則：1.時(shí)間復(fù)雜度 一個(gè)好的算法一般效率比較高。在競(jìng)賽中，試題常常會(huì)做一些算法運(yùn)行時(shí)間上的限制。這就要求我們所建立的數(shù)學(xué)模型對(duì)應(yīng)算法的效率一定要符合要求。這也是最重要的一個(gè)原則。算法評(píng)價(jià) 2.空間復(fù)雜度出于計(jì)算機(jī)自身的限制，程序在運(yùn)行時(shí)一般只被提供有限的內(nèi)存空間。這也就要求我們建立模型時(shí)顧及到這一點(diǎn)。但對(duì)于模型對(duì)應(yīng)的算法來(lái)說(shuō)，并不是要求空間越低越好，只要不超過(guò)內(nèi)存限制就可以了。 算法評(píng)價(jià) 3.編程復(fù)雜度相對(duì)而言，“編程復(fù)雜度”的要求要略低一些。但是在競(jìng)賽中，如果建立的算法實(shí)現(xiàn)起來(lái)十

6、分繁瑣，自然不利于比賽。所以，在建立模型時(shí)（特別是在競(jìng)賽中）這點(diǎn)也要納入考慮之中。 算法評(píng)價(jià) 一道題目可能對(duì)應(yīng)幾種不同思想的模型，就要根據(jù)評(píng)價(jià)模型的標(biāo)準(zhǔn)來(lái)衡量一下，確定一個(gè)模型作為分析方向。這時(shí)的評(píng)價(jià)標(biāo)準(zhǔn)除了上述的時(shí)間、空間、編程復(fù)雜度三個(gè)標(biāo)準(zhǔn)外，還要加上一個(gè)思維的復(fù)雜度。 算法評(píng)價(jià) 所謂思維的復(fù)雜度，是指思考所耗費(fèi)的時(shí)間和精力。如果我們確定了一個(gè)模型作為分析的方向（沒(méi)有考慮思維復(fù)雜度），從問(wèn)題原型到該數(shù)學(xué)模型的建模過(guò)程卻十分復(fù)雜，導(dǎo)致思維耗費(fèi)時(shí)間長(zhǎng)，精力多，那自然是不合算的?？偟膩?lái)說(shuō)，對(duì)于多種數(shù)學(xué)模型的選擇，我們遵循“邊分析，邊選擇”的原則。 影響算法效率的因素問(wèn)題的算法模型的建立問(wèn)題的數(shù)據(jù)

7、結(jié)構(gòu)選擇例題1：走迷宮問(wèn)題(maze)【題目描述】有一個(gè)n*n的迷宮，每個(gè)方格里都有著相應(yīng)的數(shù)字。你從左上角出發(fā)，每次可以向上下左右四個(gè)方向最多移動(dòng)k格，并且要求你每次到達(dá)的方格里的數(shù)字必須大于上一次所在方格的數(shù)字?，F(xiàn)在要求你走過(guò)的方格的所有數(shù)之和最大，問(wèn)這個(gè)最大和是多少。例題1：走迷宮問(wèn)題(maze)【題目描述】 有一個(gè)n*n的迷宮，每個(gè)方格里都有著相應(yīng)的數(shù)字。你從左上角出發(fā)，每次可以向上下左右四個(gè)方向最多移動(dòng)k格，并且要求你每次到達(dá)的方格里的數(shù)字必須大于上一次所在方格的數(shù)字?，F(xiàn)在要求你走過(guò)的方格的所有數(shù)之和最大，問(wèn)這個(gè)最大和是多少。【數(shù)據(jù)范圍】1 = n = 100 ，1 = k = n

8、，方格里的數(shù)最大不超過(guò)integer?！据斎胛募?maze.in。 第一行為 n 和 k，以下 n 行是一個(gè) n * n 的矩陣。【輸出文件】 maze.out。 僅一個(gè)數(shù)，為求得的最大和?！緲永斎搿? 1 3 6 24 7 92 3 1 【樣例輸出】 25 解法一基于產(chǎn)生式系統(tǒng)的搜索算法，效率極低，為指數(shù)級(jí)別的算法。解法二（動(dòng)態(tài)規(guī)劃模型一）我們首先很容易想到把矩陣?yán)梢粭l直線，然后按矩陣?yán)锏脑貜男〉酱笈判?，并用no數(shù)組表示現(xiàn)在的元素在原矩陣中的位置。設(shè)fi表示前i個(gè)數(shù)中選取第I個(gè)數(shù)所能得到的最大和，則有：fi = Max fj + ai 且aj ai，且現(xiàn)數(shù)列中元素j在原矩陣中可以達(dá)到

9、現(xiàn)數(shù)列中的元素i在原矩陣中的位置。易知所求答案為 Max fi (k = i = n)。( k 表示矩陣左上角元素在新數(shù)列中的位置)此算法時(shí)間復(fù)雜度最壞 O(n4)，空間復(fù)雜度 O(n2)。 解法三（規(guī)劃模型二）因?yàn)轭}目中明確表示一次移動(dòng)的兩個(gè)存在大小關(guān)系，設(shè)路徑為A(x1,y1),A(x2,y2)A(xl,yl)，那么可以得到A(x1,y1)A(x2,y2)A(xl,yl)，由此可以看出按照移動(dòng)的步數(shù)劃分階段不會(huì)產(chǎn)生后效性，用f(l,x,y)表示在第l步移動(dòng)到x,y步所能得到的最大和。狀態(tài)轉(zhuǎn)移：F(l,x,y)=maxf(l-1,x1,y),f(l-1,x,y1)+Ax,y (abs(x1-

10、x)=k ,abs(y1-y)=k)F(0,1,1)=A1,1時(shí)間復(fù)雜度為o(L*n2*k)?？臻g復(fù)雜度 O(n3)。解法四（規(guī)劃模型三） 我們用fi,j表示到達(dá)矩陣(i,j)位置時(shí)所能得到的最大和，由于題目對(duì)遞增序列的要求，使得這道題目不用轉(zhuǎn)換成一維數(shù)列就可以直接進(jìn)行規(guī)劃，規(guī)劃方程為：fi,j = Max fi1,j1 + ai,j （ai1,j1 ai,j）其中（i1,j1）表示從（i,j）通過(guò)允許的移動(dòng)可以到達(dá)的位置，則所求答案即為 Max fi,j (1 = i,j = n)。此算法的時(shí)間復(fù)雜度 O(n*n*k)，空間復(fù)雜度 O(n2)。解法五（圖論模型）以迷宮的每個(gè)房間為點(diǎn)，如果(a

11、,b)可以移動(dòng)到(c,d)，那么就從(a,b)引出一條有向邊到(c,d)，邊上的權(quán)值為A(c,d)，建立一張有向圖,然后以A(1,1)點(diǎn)為源點(diǎn)求最長(zhǎng)路。用SPFA實(shí)現(xiàn)，大概的時(shí)間復(fù)雜度為o(n2*k)。不同數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的影響乘船問(wèn)題：有N個(gè)人需要乘船，而每條船最多只能載兩人，且必須同名或同姓。求最少需要多少條船。問(wèn)題分析看到這道題，很多人都會(huì)想到圖的數(shù)據(jù)結(jié)構(gòu)：將N個(gè)人看作無(wú)向圖的N個(gè)點(diǎn)，凡同名或同姓的人之間都連上邊。要滿足用船最少的條件，就是需要盡量多的兩人共乘一條船，表現(xiàn)在圖中就是要用最少的邊完成對(duì)所有頂點(diǎn)的覆蓋。這就正好對(duì)應(yīng)了圖論的典型問(wèn)題：求最小邊的覆蓋。所用的算法為“求任意圖最大

12、匹配”的算法。分析使用“求任意圖最大匹配”的算法比較復(fù)雜(要用到擴(kuò)展交錯(cuò)樹(shù)，對(duì)花的收縮等等)，效率也不是很高。因此，我們必須尋找一個(gè)更簡(jiǎn)單高效的方法。首先，由于圖中任兩個(gè)連通分量都是相對(duì)獨(dú)立的，也就是說(shuō)任一條匹配邊的兩頂點(diǎn)，都只屬于同一個(gè)連通分量。因此，我們可以對(duì)每個(gè)連通分量分別進(jìn)行處理，而不會(huì)影響最終的結(jié)果。采用圖的數(shù)據(jù)結(jié)構(gòu)得出的算法為： 每次輸出一條非橋的邊，并從圖中將邊的兩頂點(diǎn)刪去。 此算法的時(shí)間復(fù)雜度為O(n3)。（尋找一條非橋邊的復(fù)雜度為O(n2)，尋找覆蓋邊操作的復(fù)雜度為O(n)）采用樹(shù)結(jié)構(gòu)解決首先，我們以連通分量中任一個(gè)頂點(diǎn)作為樹(shù)根，然后我們來(lái)確定建樹(shù)的方法：（1）找出與根結(jié)點(diǎn)i

13、同姓的點(diǎn)j（j不在二叉樹(shù)中）作為i的左兒子，再以j為樹(shù)根建立子樹(shù)。（2）找出與根結(jié)點(diǎn)i同名的點(diǎn)k（k不在二叉樹(shù)中）作為i的右兒子，再以k為樹(shù)根建立子樹(shù)。 我們還可以對(duì)需要船只s的下限進(jìn)行估計(jì)：對(duì)于一個(gè)包含Pi個(gè)頂點(diǎn)的連通分量，其最小覆蓋邊數(shù)顯然為Pi/2。若圖中共有L個(gè)連通分量，則s=Pi/2(1=i=L)。 然后，我們通過(guò)多次嘗試，可得出一個(gè)猜想：實(shí)際需要的覆蓋邊數(shù)完全等于我們求出的下限Pi/2(1=i=L)。 兩點(diǎn)間用實(shí)線表示同姓，虛線表示同名結(jié)論及其證明結(jié)論1： 以連通分量中的任一點(diǎn)p作為根結(jié)點(diǎn)的二叉樹(shù)，必然能夠包含連通分量中的所有頂點(diǎn)。結(jié)論2： 包含m個(gè)結(jié)點(diǎn)的二叉樹(shù)Tm，只需要船的數(shù)量

14、為boatm=m/2(mN)。如何證明？ 采用數(shù)學(xué)歸納法(見(jiàn)文本“論文”)如何輸出具體的乘船方案proc try(father:integer;var root:integer;var rest:byte);輸出root為樹(shù)根的子樹(shù)的乘船方案，father=0表示root是其父親的左兒子，father=1表示root是其父親的右兒子，rest表示輸出子樹(shù)的乘船方案后，是否還剩下一個(gè)根結(jié)點(diǎn)未乘船beginvisitroot:=true; 標(biāo)記root已訪問(wèn)找到一個(gè)與root同姓且未訪問(wèn)的結(jié)點(diǎn)j; if jn+1 then try(0,j,lrest);找到一個(gè)與root同姓且未訪問(wèn)的結(jié)點(diǎn)k; i

15、f kn+1 then try(1,k,rrest);if (lrest=1) xor (rrest=1) then begin 判斷root是否只有一個(gè)兒子，情況一if lrest=1 then print(lrest,root) else print(rrest,root);rest:=0;endelse if (lrest=1) and (rrest=1) then begin 判斷root是否有兩個(gè)兒子if father=0 then beginprint(rrest,root);root:=j; 情況二end else beginprint(lrest,root);root:=k;

16、情況三End;rest:=1;endelse rest:=1;end; 這只是輸出一棵二叉樹(shù)的乘船方案的算法，要輸出所有人的乘船方案，我們還需再加一層循環(huán)，用于尋找各棵二叉樹(shù)的根結(jié)點(diǎn)，但由于每個(gè)點(diǎn)都只會(huì)訪問(wèn)一次，尋找其左右兒子各需進(jìn)行一次循環(huán)，所以算法的時(shí)間復(fù)雜度為O(n2)。分治思想分治(divide-and-conquer)就是“分而治之”的意思，其實(shí)質(zhì)就是將原問(wèn)題分成n個(gè)規(guī)模較小而結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題；然后遞歸地解這些子問(wèn)題，最后合并其結(jié)果就得到原問(wèn)題的解。其三個(gè)步驟如下；分解(Divide)：將原問(wèn)題分成一系列子問(wèn)題。解決(Conquer)：遞歸地解各子問(wèn)題。若子問(wèn)題足夠小，則可直

17、接求解。合并(combine)；將子問(wèn)題的結(jié)果合并成原問(wèn)題的解。 例題分析1 0-1序列考慮這樣一個(gè)序列”110100100010000”就是”1” + ”10”+”100”+”1000”+要求求出第I位是0 還是1。Input:第一行：N，測(cè)試點(diǎn)的個(gè)數(shù)；(N 0)；Output:對(duì)每個(gè)測(cè)試點(diǎn)輸出0 或 1，每行一個(gè)數(shù)；Sample Input: (bit.in)31 2 3Sample Output: (bit.out)110電纜老板（MASTER） 某地區(qū)即將舉行區(qū)域程序設(shè)計(jì)比賽，競(jìng)賽委員會(huì)已經(jīng)成立并決定舉行一次最公平的競(jìng)賽，他們決定利用星形拓?fù)浣Y(jié)構(gòu)來(lái)連接每個(gè)競(jìng)賽者的電腦-也即連接這些電腦

18、到一個(gè)中心HUB上；為了達(dá)到真正的公平競(jìng)賽目的，競(jìng)賽委員會(huì)主任下令要求：每個(gè)競(jìng)賽電腦連接到中心HUB的電纜必須是一樣長(zhǎng)的。競(jìng)賽委員會(huì)聯(lián)系了一個(gè)本地的電纜老板，要求老板為他們提供一定量的相同長(zhǎng)度的電纜，而且要求電纜長(zhǎng)度越長(zhǎng)越好。通過(guò)調(diào)查，電纜老板知道倉(cāng)庫(kù)中每根電纜的長(zhǎng)度（精確到厘米），而且他可以以厘米的精度剪斷電纜，但確不知道他能為競(jìng)賽委員會(huì)提供的每根電纜的最大長(zhǎng)度是多少？你的任務(wù)就是：編程求出每根電纜的最大可能的長(zhǎng)度。輸入： 第1行，2個(gè)整數(shù)N和K，N是倉(cāng)庫(kù)中的電纜條數(shù)，K是競(jìng)賽委員會(huì)要求的電纜條數(shù)。其中1N1000, 1K10000。 第2N+1行，每行為倉(cāng)庫(kù)中的一條電纜的長(zhǎng)度，單位為米。輸

19、出：僅1行，為提供給競(jìng)賽委員的電纜最大長(zhǎng)度（精確到小數(shù)點(diǎn)兩位）輸入輸出示例：MASTERIN MASTEROUT4 11 2.008.027.434.575.39例題3：圖形中點(diǎn)的個(gè)數(shù)給定平面上N個(gè)圖形(矩形或圓)以及M個(gè)點(diǎn)后，請(qǐng)你求出每個(gè)點(diǎn)在多少個(gè)矩形或圓內(nèi)部(這里假設(shè)矩形的邊都平行于坐標(biāo)軸)。注意：當(dāng)某點(diǎn)在一個(gè)圖形的邊界上時(shí)，我們認(rèn)為該點(diǎn)不在這個(gè)圖形的內(nèi)部分析原始的解決方案：就是兩兩都判一次。優(yōu)化：就是先將點(diǎn)按x排序。如果圖形是矩形,那就先二分查找在x1, x2范圍內(nèi)的那一段,對(duì)于段內(nèi)的每一個(gè)點(diǎn)只用看看y在不在范圍內(nèi)就可以了。如果圖形是圓,那就先二分查找在x-r, x+r范圍內(nèi)的那一段,對(duì)

20、于段內(nèi)的每一個(gè)點(diǎn)再看看到圓心的距離。這樣程序的最壞效率是O(lgM*N*M)例題4：消除隱藏線在計(jì)算機(jī)輔助設(shè)計(jì)(CAD)中，有一個(gè)經(jīng)典問(wèn)題：消除隱藏線（被其它圖形遮住的線段）。你需要設(shè)計(jì)一個(gè)軟件，幫助建筑師繪制城市的側(cè)視輪廓圖。為了方便處理，限定所有的建筑物都是矩形的，而且全部建立在同一水平面上。每個(gè)建筑物用一個(gè)三元組表示(Li,Hi,Ri)其中Li和Ri分別是建筑物i 的左右邊緣坐標(biāo)，Hi是建筑物i的高度。下面左圖中的建筑物分別用如下三元組表示：(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,

21、28)下面圖中的城市側(cè)視輪廓線用如下的序列表示：(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)分析本題其實(shí)是矩形覆蓋問(wèn)題的特殊情形固定了矩形的下邊界。本題可以使用矩形切割或者離散化加上線段樹(shù)解決，但是前者的時(shí)間復(fù)雜度在最壞情況下可能達(dá)到O(n3)，而后者的編程實(shí)現(xiàn)比較復(fù)雜。要求n個(gè)矩形的輪廓，先將這n個(gè)矩形分成兩個(gè)大小相等的部分，分別求其輪廓，然后再將這兩個(gè)輪廓合并。規(guī)模為1的問(wèn)題可以直接解決。具體來(lái)說(shuō)，如果這個(gè)矩形的三元組表示為(L,H,R)，那么其輪廓為(L,H,R,0)。對(duì)于規(guī)模為k的問(wèn)題，假設(shè)得到了兩個(gè)規(guī)模為k/2的輪廓，分別為A和B，我們?nèi)绾蔚玫胶喜⒑蟮妮喞狢？首先，容易證明輪廓C的每一個(gè)橫坐標(biāo)，都來(lái)源于輪廓A和B的橫坐標(biāo)，而不會(huì)產(chǎn)生新的坐標(biāo)值。因此，我們只需計(jì)算A和B中所有涉及到的橫坐標(biāo)在C中的高度。由于輪廓C中的橫坐標(biāo)值要求有序，我們可以