1、算法效率與分治算法的運用長沙市一中曹利國算法效率的評價 n算法的評價算法的評價 n有時求解同一個問題經常有多種可用的有時求解同一個問題經常有多種可用的算法，在一定的條件下當然要選擇運用算法，在一定的條件下當然要選擇運用好的算法。用什么方法評價算法的好壞好的算法。用什么方法評價算法的好壞呢？通常運用算法復雜性這一概念來評呢？通常運用算法復雜性這一概念來評價算法。價算法。 算法評價 n算法執(zhí)行時間需經過根據該算法編制的程序在計算機上運轉時所耗費的時間來度量。而度量一個程序的執(zhí)行時間通常有兩種方法： n事后統(tǒng)計的方法 n事前分析估算的方法 算法評價 n一個用高級程序文語編寫的程序在計算機上運轉時所耗

2、費的時間取決于以下要素：n根據的算法選用何種戰(zhàn)略；n問題的規(guī)模.例如求100以內還是1000以內的素數(shù)；n書寫程序的言語.對于同一個算法,實現(xiàn)言語的級別越高,執(zhí)行效率就越低；n編譯程序所產生的機器代碼的質量；n機器執(zhí)行指令的速度。 算法評價 n一個算法是由控制構造順序、分支和循環(huán)三種和原操作指固有數(shù)據類型的操作構成的，那么算法時間取決于兩者的綜合效果。 n為了便于比較同一問題的不同算法，經過的做法是，從算法中選取一種對于所研討的問題或算法類型來說是根本運算的原操作，以該根本操作反復執(zhí)行的次數(shù)作為算法的時間度量。 算法評價 n普通情況下，算法中根本操作反復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)fn，算

3、法的時間量度記作nTn= Ofnn它表示問題規(guī)模n的增大算法執(zhí)行時間的增長率和fn的增長率一樣，稱作算法的漸進時間復雜度，簡稱時間復雜度。算法評價 n例如：在以下三個程序段中，nx:=x+1nfor i:=1 to n do x:=x+1;nfor j:=1 to n do n for k:=1 to n do x:=x+1n含根本操作“x增1的語句x:=x+1的頻度分別為1，n和 n2 ，那么這三個程序段的時間復雜度分別為O1，On，On2，分別稱為常量階、線性階和平方階。 算法評價 n算法還能夠呈現(xiàn)的時間復雜度有：對數(shù)階Olog n，指數(shù)階O2n等。在n很大時, 不同數(shù)量級時間復雜度顯然有

4、O1Olog nOnOnlog nOn2 On3O2n，可以看出，在算法設計時，我們應該盡能夠選用多項式階O(nk)的算法，而不希望用指數(shù)階的算法。 算法評價 n由于算法的時間復雜度思索的只是對于問題規(guī)模n的增長率，那么在難以計算根本操作執(zhí)行次數(shù)(或語句頻度)的情況下，只需求出它關于n的增長率或階即可。n例如，在以下程序段中：nfor i:=2 to n do n for j:=2 to i-1 do x:=x+1n語句x:=x+1執(zhí)行次數(shù)關于n的增長率為n2，它是語句頻度表達式(n-1)(n-2)/2中增長最快的一項。 算法評價 n類似于算法的時間復雜度，以空間復雜度作為算法所需存儲空間的量

5、度，記作nS(n)=O(f(n) n其中n為問題的規(guī)模(或大小)。一個上機執(zhí)行的程序除了需求存儲空間來存放本身所用指令、常數(shù)、變量和輸入數(shù)據外，也需求一些對數(shù)據進展操作的任務單元和存儲一些為實現(xiàn)計算所需信息的輔助空間。 算法評價 n評價一個數(shù)學模型有以下幾個原那么：n1.時間復雜度n一個好的算法普通效率比較高。在競賽中，試題經常會做一些算法運轉時間上的限制。這就要求我們所建立的數(shù)學模型對應算法的效率一定要符合要求。這也是最重要的一個原那么。算法評價 n2.2.空間復雜度空間復雜度n出于計算機本身的限制，程序在出于計算機本身的限制，程序在運轉時普通只被提供有限的內存空間。運轉時普通只被提供有限的

6、內存空間。這也就要求我們建立模型時顧及到這一這也就要求我們建立模型時顧及到這一點。但對于模型對應的算法來說，并不點。但對于模型對應的算法來說，并不是要求空間越低越好，只需不超越內存是要求空間越低越好，只需不超越內存限制就可以了。限制就可以了。 算法評價 n3.3.編程復雜度編程復雜度n相對而言，相對而言，“編程復雜度的要編程復雜度的要求要略低一些。但是在競賽中，假設建求要略低一些。但是在競賽中，假設建立的算法實現(xiàn)起來非常繁瑣，自然不利立的算法實現(xiàn)起來非常繁瑣，自然不利于競賽。所以，在建立模型時特別是于競賽。所以，在建立模型時特別是在競賽中這點也要納入思索之中。在競賽中這點也要納入思索之中。 影

7、響算法效率的要素n問題的算法模型的建立n問題的數(shù)據構造選擇算法評價 n一道標題能夠對應幾種不同思想的模型，就要根據評價模型的規(guī)范來衡量一下，確定一個模型作為分析方向。這時的評價規(guī)范除了上述的時間、空間、編程三個規(guī)范外，還要加上一個思想的復雜度。 算法評價 n所謂思想的復雜度，是指思索所耗費的時間和精神。假設我們確定了一個模型作為分析的方向沒有思索思想復雜度，從問題原型到該數(shù)學模型的建模過程卻非常復雜，導致思想耗費時間長，精神多，那自然是不合算的?？偟膩碚f，對于多種數(shù)學模型的選擇，我們遵照“邊分析，邊選擇的原那么。 不同數(shù)據構造對算法效率的影響乘船問題：有N個人需求乘船，而每船最多只能載兩人，且

8、必需同名或同姓。求最少需求多少條船。問題分析n看到這道題，很多人都會想到圖的數(shù)據構造：將N個人看作無向圖的N個點，凡同名或同姓的人之間都連上邊。n要滿足用船最少的條件，就是需求盡量多的兩人共乘一條船，表如今圖中就是要用最少的邊完成對一切頂點的覆蓋。這就正好對應了圖論的典型問題：求最小邊的覆蓋。所用的算法為“求恣意圖最大匹配的算法。分析n運用“求恣意圖最大匹配的算法比較復雜(要用到擴展交錯樹，對花的收縮等等)，效率也不是很高。因此，我們必需尋覓一個更簡單高效的方法。n首先，由于圖中任兩個連通分量都是相對獨立的，也就是說任一條匹配邊的兩頂點，都只屬于同一個連通分量。因此，我們可以對每個連通分量分別

9、進展處置，而不會影響最終的結果。n同時，我們還可以對需求船只s的下限進展估計：n對于一個包含Pi個頂點的連通分量，其最小覆蓋邊數(shù)顯然為Pi/2。假設圖中共有L個連通分量，那么s=Pi/2(1=i=L)。n 然后，我們經過多次嘗試，可得出一個猜測：n實踐需求的覆蓋邊數(shù)完全等于我們求出的下限Pi/2(1=i=L)。n采用圖的數(shù)據構造得出的算法為：n 每次輸出一條非橋的邊，并從圖中將邊的兩頂點刪去。n 此算法的時間復雜度為O(n3)。n尋覓一條非橋邊的復雜度為O(n2)，尋覓覆蓋邊操作的復雜度為O(n)采用樹構造處理n首先，我們以連通分量中任一個頂點作為樹根，然后我們來確定建樹的方法：n1找出與根結

10、點i同姓的點jj不在二叉樹中作為i的左兒子，再以j為樹根建立子樹。n2找出與根結點i同名的點kk不在二叉樹中作為i的右兒子，再以k為樹根建立子樹。證明n包含m個結點的二叉樹Tm，只需求船的數(shù)量為boatm=m/2(mN)。nproc try(father:integer;var root:integer;var rest:byte);n輸出root為樹根的子樹的乘船方案，father=0表示root是其父親的左兒子，nfather=1表示root是其父親的右兒子，rest表示輸出子樹的乘船方案后，n能否還剩下一個根結點未乘船beginvisitroot:=true; 標志root已訪問找到一個

11、與root同姓且未訪問的結點j; if jn+1 then try(0,j,lrest);找到一個與root同姓且未訪問的結點k; if kn+1 then try(1,k,rrest);nif (lrest=1) xor (rrest=1) then begin 判別root能否只需一個兒子，情況一nif lrest=1 then print(lrest,root) else print(rrest,root);nrest:=0;nendnelse if (lrest=1) and (rrest=1) then begin 判別root能否有兩個兒子if father=0 then begi

12、nprint(rrest,root);root:=j; 情況二end else beginprint(lrest,root);root:=k; 情況三End;rest:=1;endelse rest:=1;end; 這只是輸出一棵二叉樹的乘船方案的算法，要輸出一切人的乘船方案，我們還需再加一層循環(huán)，用于尋覓各棵二叉樹的根結點，但由于每個點都只會訪問一次，尋覓其左右兒子各需進展一次循環(huán)，所以算法的時間復雜度為O(n2)。分治思想分治思想n假設在將規(guī)模為n的問題分成k個不同子集合的情況下，能得到k個不同的可分別求解的子問題，其中1k=n，而且在求出了這些子問題的解之后，還可找到適當?shù)姆椒ò阉鼈兒喜?/p>

13、成整個問題的解，那么，具備上述特性的問題可思索運用分治戰(zhàn)略設計求解。這種設計求解的思想就是將整個問題分成假設干個小問題后分而治之。 分治思想分治思想n分治(divide-and-conquer)就是“分而治之的意思，其本質就是將原問題分成n個規(guī)模較小而構造與原問題類似的子問題；然后遞歸地解這些子問題，最后合并其結果就得到原問題的解。其三個步驟如下；n分解(Divide)：將原問題分成一系列子問題。n處理(Conquer)：遞歸地解各子問題。假設子問題足夠小，那么可直接求解。n合并(combine)；將子問題的結果合并成原問題的解。 分治思想分治思想問題S問題S問題SS的解問題S1問題S2問題S

14、i問題SnS1的解S2的解Si的解Sn的解問題的分解子集解的合并子問題求解分治思想分治思想n由分治法所得到的子問題與原問題具有一樣的類型。假設得到的子問題相對來說還太大，那么可反復運用分治戰(zhàn)略將這些子問題分成更小的同類型子問題，直至產生出不用進一步細分就可求解的子問題。分治求解可用一個遞歸過程來表示。n要使分治算法效率高，關鍵在于如何分割？普通地，出于一種平衡原那么，總是把大問題分成K個規(guī)模盡能夠相等的子問題，但也有例外，如求表的最大最小元問題的算法，當n6時，等分定量成兩個規(guī)模為3的子表L1和L2不是最正確分割。例題1：消除隱藏線n在計算機輔助設計(CAD)中，有一個經典問題：消除隱藏線被其

15、它圖形遮住的線段。他需求設計一個軟件，協(xié)助建筑師繪制城市的側視輪廓圖。為了方便處置，限定一切的建筑物都是矩形的，而且全部建立在同一程度面上。每個建筑物用一個三元組表示(Li,Hi,Ri)其中Li和Ri分別是建筑物i 的左右邊緣坐標，Hi是建筑物i的高度。n下面左圖中的建筑物分別用如下三元組表示：n(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3n,25),(19,18,22),(23,13,29),(24,4,28)n下面圖中的城市側視輪廓線用如下的序列表示：n(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)分析n

16、此題其實是矩形覆蓋問題的特殊情形固定了矩形的下邊境。此題可以運用矩形切割或者離散化加上線段樹處理，但是前者的時間復雜度在最壞情況下能夠到達O(n3)，而后者的編程實現(xiàn)比較復雜。n要求n個矩形的輪廓，先將這n個矩形分成兩個大小相等的部分，分別求其輪廓，然后再將這兩個輪廓合并。n規(guī)模為1的問題可以直接處理。詳細來說，假設這個矩形的三元組表示為(L,H,R)，那么其輪廓為(L,H,R,0)。n對于規(guī)模為k的問題，假設得到了兩個規(guī)模為k/2的輪廓，分別為A和B，我們如何得到合并后的輪廓C？首先，容易證明輪廓C的每一個橫坐標，都來源于輪廓A和B的橫坐標，而不會產生新的坐標值。因此，我們只需計算A和B中一

17、切涉及到的橫坐標在C中的高度。n由于輪廓C中的橫坐標值要求有序，我們可以仿照歸并排序的方法，用兩個指針掃描輪廓A和B。n 詳細的方法是，設指針i指向輪廓A的當前橫坐標，指針j指向輪廓B的當前橫坐標。假設指針i指向的橫坐標較小，那么將這一橫坐標參與到C中，且在C中的高度為A中第i個橫坐標對應的高度與B中第j-1個橫坐標對應的高度的最大值。n然后將指針i向后移一位；指針j指向的橫坐標較小的情況那么類似處置。假設兩個指針指向的橫坐標一樣，此時只需將這一橫坐標參與到C中一次，且高度為兩指針指向高度的最大值，然后將兩指針同時向后移一位。最后，需求掃描一遍輪廓C，將相鄰的高度一樣的橫坐標合并。n分析時間復

18、雜度，T(n)=O(nlogn)?？臻g方面，由于遞歸的層數(shù)為O(logn)，每一層需求保管O(n)的空間，所以總的空間復雜度為O(nlogn)。例題2：Bone Sort(ZJU1440)n求一個未排序的序列需求經過多少次交換操作才干使序列升序有序，并且求出原序列中有多少個逆序對。n算法思想：算法思想：n按照順序掃描序列的每一位，假設此位尚未按照順序掃描序列的每一位，假設此位尚未調整至升序要求那么進展一次交換。調整至升序要求那么進展一次交換。詳細實現(xiàn)：詳細實現(xiàn)：1預處置：對原序列升序排序復雜度O(NLog2N)。2依次檢查原序列的每一位復雜度O(N)： 判別該位置目前的值能否與排序后的等位的值一樣 一樣那么繼續(xù)檢查下一位 否那么將當前位置值與排序后等位的值所在的位置交換，更新交換次數(shù)求逆序對n求逆序對有多種方法， 目前運用比較廣泛且實現(xiàn)比較簡單的主要有三種算法：n1、歸并排序n2、線段樹n3、樹狀數(shù)組歸并排序方法求逆序對 假設當前需求歸并l, mid 和mid+1, r 兩段區(qū)間，設前一段區(qū)間當前指針為p， 后一段區(qū)間指針為q。假設當前存在apaq 那么可知p, mid這段區(qū)間內一切的數(shù)都與aq構成一個逆序對，那么把ans 值加上mid-p+1 就行了。歸并排序求逆序對的時間復雜度為o(n*logn)，空間復雜度也只需o(