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

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

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

3、法的時(shí)間量度記作nTn= Ofnn它表示問(wèn)題規(guī)模n的增大算法執(zhí)行時(shí)間的增長(zhǎng)率和fn的增長(zhǎng)率一樣，稱(chēng)作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。算法評(píng)價(jià) n例如：在以下三個(gè)程序段中，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的語(yǔ)句x:=x+1的頻度分別為1，n和 n2 ，那么這三個(gè)程序段的時(shí)間復(fù)雜度分別為O1，On，On2，分別稱(chēng)為常量階、線(xiàn)性階和平方階。 算法評(píng)價(jià) n算法還能夠呈現(xiàn)的時(shí)間復(fù)雜度有：對(duì)數(shù)階Olog n，指數(shù)階O2n等。在n很大時(shí), 不同數(shù)量級(jí)時(shí)間復(fù)雜度顯然有

4、O1Olog nOnOnlog nOn2 On3O2n，可以看出，在算法設(shè)計(jì)時(shí)，我們應(yīng)該盡能夠選用多項(xiàng)式階O(nk)的算法，而不希望用指數(shù)階的算法。 算法評(píng)價(jià) n由于算法的時(shí)間復(fù)雜度思索的只是對(duì)于問(wèn)題規(guī)模n的增長(zhǎng)率，那么在難以計(jì)算根本操作執(zhí)行次數(shù)(或語(yǔ)句頻度)的情況下，只需求出它關(guān)于n的增長(zhǎng)率或階即可。n例如，在以下程序段中：nfor i:=2 to n do n for j:=2 to i-1 do x:=x+1n語(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à) n類(lèi)似于算法的時(shí)間復(fù)雜度，以空間復(fù)雜度作為算法所需存儲(chǔ)空間的量

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

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

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

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

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

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

11、與root同姓且未訪(fǎng)問(wèn)的結(jié)點(diǎn)j; if jn+1 then try(0,j,lrest);找到一個(gè)與root同姓且未訪(fǎng)問(wèn)的結(jié)點(diǎn)k; if kn+1 then try(1,k,rrest);nif (lrest=1) xor (rrest=1) then begin 判別root能否只需一個(gè)兒子，情況一nif lrest=1 then print(lrest,root) else print(rrest,root);nrest:=0;nendnelse if (lrest=1) and (rrest=1) then begin 判別root能否有兩個(gè)兒子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; 這只是輸出一棵二叉樹(shù)的乘船方案的算法，要輸出一切人的乘船方案，我們還需再加一層循環(huán)，用于尋覓各棵二叉樹(shù)的根結(jié)點(diǎn)，但由于每個(gè)點(diǎn)都只會(huì)訪(fǎng)問(wèn)一次，尋覓其左右兒子各需進(jìn)展一次循環(huán)，所以算法的時(shí)間復(fù)雜度為O(n2)。分治思想分治思想n假設(shè)在將規(guī)模為n的問(wèn)題分成k個(gè)不同子集合的情況下，能得到k個(gè)不同的可分別求解的子問(wèn)題，其中1k=n，而且在求出了這些子問(wèn)題的解之后，還可找到適當(dāng)?shù)姆椒ò阉鼈兒喜?/p>

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

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

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

16、此題其實(shí)是矩形覆蓋問(wèn)題的特殊情形固定了矩形的下邊境。此題可以運(yùn)用矩形切割或者離散化加上線(xiàn)段樹(shù)處理，但是前者的時(shí)間復(fù)雜度在最壞情況下能夠到達(dá)O(n3)，而后者的編程實(shí)現(xiàn)比較復(fù)雜。n要求n個(gè)矩形的輪廓，先將這n個(gè)矩形分成兩個(gè)大小相等的部分，分別求其輪廓，然后再將這兩個(gè)輪廓合并。n規(guī)模為1的問(wèn)題可以直接處理。詳細(xì)來(lái)說(shuō)，假設(shè)這個(gè)矩形的三元組表示為(L,H,R)，那么其輪廓為(L,H,R,0)。n對(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中一

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

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