算法效率分析與分治法的應用

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

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

3、下列三個程序段中，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”的語句x:=x+1的頻度分別為1，n和 n2 ，則這三個程序段的時間復雜度分別為O（1），O（n），O（n2），分別稱為常量階、線性階和平方階。 算法評價 算法還可能呈現(xiàn)的時間復雜度有：對數(shù)階O（log n），指數(shù)階O（2n）等。在n很大時, 不同數(shù)量級時間復雜度顯然有O（1）O（log n）O（n）O（nlog n）O（n2） O（n3）O（2n），可以看出，在算法設計時，我們應該盡可能選用多項式階O(nk)的算法，

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

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

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

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

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

9、現(xiàn)數(shù)列中的元素i在原矩陣中的位置。易知所求答案為 Max fi (k = i = n)。( k 表示矩陣左上角元素在新數(shù)列中的位置)此算法時間復雜度最壞 O(n4)，空間復雜度 O(n2)。 解法三（規(guī)劃模型二）因為題目中明確表示一次移動的兩個存在大小關系，設路徑為A(x1,y1),A(x2,y2)A(xl,yl)，那么可以得到A(x1,y1)A(x2,y2)A(xl,yl)，由此可以看出按照移動的步數(shù)劃分階段不會產(chǎn)生后效性，用f(l,x,y)表示在第l步移動到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時間復雜度為o(L*n2*k)。空間復雜度 O(n3)。解法四（規(guī)劃模型三） 我們用fi,j表示到達矩陣(i,j)位置時所能得到的最大和，由于題目對遞增序列的要求，使得這道題目不用轉(zhuǎn)換成一維數(shù)列就可以直接進行規(guī)劃，規(guī)劃方程為：fi,j = Max fi1,j1 + ai,j （ai1,j1 ai,j）其中（i1,j1）表示從（i,j）通過允許的移動可以到達的位置，則所求答案即為 Max fi,j (1 = i,j = n)。此算法的時間復雜度 O(n*n*k)，空間復雜度 O(n2)。解法五（圖論模型）以迷宮的每個房間為點，如果(a

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

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

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

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

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

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

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

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

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

20、于段內(nèi)的每一個點再看看到圓心的距離。這樣程序的最壞效率是O(lgM*N*M)例題4：消除隱藏線在計算機輔助設計(CAD)中，有一個經(jīng)典問題：消除隱藏線（被其它圖形遮住的線段）。你需要設計一個軟件，幫助建筑師繪制城市的側(cè)視輪廓圖。為了方便處理，限定所有的建筑物都是矩形的，而且全部建立在同一水平面上。每個建筑物用一個三元組表示(Li,Hi,Ri)其中Li和Ri分別是建筑物i 的左右邊緣坐標，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)分析本題其實是矩形覆蓋問題的特殊情形固定了矩形的下邊界。本題可以使用矩形切割或者離散化加上線段樹解決，但是前者的時間復雜度在最壞情況下可能達到O(n3)，而后者的編程實現(xiàn)比較復雜。要求n個矩形的輪廓，先將這n個矩形分成兩個大小相等的部分，分別求其輪廓，然后再將這兩個輪廓合并。規(guī)模為1的問題可以直接解決。具體來說，如果這個矩形的三元組表示為(L,H,R)，那么其輪廓為(L,H,R,0)。對于規(guī)模為k的問題，假設得到了兩個規(guī)模為k/2的輪廓，分別為A和B，我們?nèi)绾蔚玫胶喜⒑蟮妮喞狢？首先，容易證明輪廓C的每一個橫坐標，都來源于輪廓A和B的橫坐標，而不會產(chǎn)生新的坐標值。因此，我們只需計算A和B中所有涉及到的橫坐標在C中的高度。由于輪廓C中的橫坐標值要求有序，我們可以