算法201403-分治2

1、1 棋盤覆蓋與最接近點(diǎn)對(duì)問(wèn)題棋盤覆蓋與最接近點(diǎn)對(duì)問(wèn)題2 減治法減治法3 分治法小結(jié)分治法小結(jié)第第2 2章章 分治與遞歸算法（分治與遞歸算法（2 2）棋盤覆蓋問(wèn)題棋盤覆蓋問(wèn)題n一個(gè)一個(gè)2k2k的特殊棋盤是其中含有一個(gè)特殊方格的特殊棋盤是其中含有一個(gè)特殊方格的棋盤，如左下圖為的棋盤，如左下圖為k=2的一個(gè)特殊棋盤。的一個(gè)特殊棋盤。n現(xiàn)在任意給定一個(gè)現(xiàn)在任意給定一個(gè)2k2k的特殊棋盤，要用右的特殊棋盤，要用右下圖所示的下圖所示的L型骨牌來(lái)無(wú)重疊的覆蓋它。型骨牌來(lái)無(wú)重疊的覆蓋它。 1112223334445在在2k2k的的棋盤覆蓋棋盤覆蓋中要用到中要用到(4k1)/3個(gè)個(gè)L型骨牌。型骨牌。55棋盤覆蓋

2、問(wèn)題分析棋盤覆蓋問(wèn)題分析n當(dāng)當(dāng)k0時(shí)，將時(shí)，將2k2k的棋盤分割成的棋盤分割成4個(gè)個(gè)2k12k1的的子棋盤，如右下圖所示：子棋盤，如右下圖所示：2k12k12k12k12k12k12k12k1然而，這樣一來(lái)四個(gè)子棋盤的情形就不一致了。因?yàn)檫f歸求解是將問(wèn)題歸結(jié)到較小的規(guī)模的同一問(wèn)題，到較小的規(guī)模的同一問(wèn)題，所以就需要將三個(gè)正常子所以就需要將三個(gè)正常子棋盤也轉(zhuǎn)化成特殊棋盤。棋盤也轉(zhuǎn)化成特殊棋盤。為此，可以用一個(gè)為此，可以用一個(gè)L型骨型骨牌來(lái)覆蓋其余三個(gè)子棋盤牌來(lái)覆蓋其余三個(gè)子棋盤的的會(huì)合處會(huì)合處，如左圖所示。，如左圖所示。這樣原問(wèn)題轉(zhuǎn)化成了四個(gè)較小規(guī)模的子問(wèn)題。遞歸地分割下去直至單格棋盤。n特殊方

3、格必定位于特殊方格必定位于4個(gè)子棋盤之一中。個(gè)子棋盤之一中。棋盤覆蓋算法設(shè)計(jì)棋盤覆蓋算法設(shè)計(jì)n棋盤覆蓋棋盤覆蓋(參數(shù)表參數(shù)表)nn 如果是單個(gè)格子，則返回；如果是單個(gè)格子，則返回；n 將棋盤劃分成尺寸為一半的子棋盤；將棋盤劃分成尺寸為一半的子棋盤；n 判斷特殊方格在哪個(gè)子棋盤中，再用相應(yīng)的骨判斷特殊方格在哪個(gè)子棋盤中，再用相應(yīng)的骨牌覆蓋相應(yīng)牌覆蓋相應(yīng)結(jié)合部結(jié)合部，并記下它們的位置；，并記下它們的位置；n 依次對(duì)左上角、右上角、左下角和右下角這四依次對(duì)左上角、右上角、左下角和右下角這四個(gè)子棋盤進(jìn)行棋盤覆蓋；個(gè)子棋盤進(jìn)行棋盤覆蓋；nn設(shè)設(shè)T(k)是棋盤覆蓋算法覆蓋是棋盤覆蓋算法覆蓋2k2k的棋盤所

4、需要的的棋盤所需要的時(shí)間，則從算法的分治策略可知，時(shí)間，則從算法的分治策略可知， T(k)滿足如下滿足如下遞歸方程：遞歸方程：棋盤覆蓋算法的復(fù)雜性棋盤覆蓋算法的復(fù)雜性T(k) =O(1) k = 04T(k1) + O(1) k0n解此遞歸方程可得解此遞歸方程可得T(k) = O(4k)。n由于覆蓋由于覆蓋2k2k的棋盤要用的棋盤要用 (4k1)/3個(gè)個(gè)L型骨牌，型骨牌，故此算法是一個(gè)在漸進(jìn)意義下最優(yōu)的算法。故此算法是一個(gè)在漸進(jìn)意義下最優(yōu)的算法。最接近點(diǎn)對(duì)問(wèn)題最接近點(diǎn)對(duì)問(wèn)題n給定平面上給定平面上n個(gè)點(diǎn)，在個(gè)點(diǎn)，在n個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，找個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，找出其中相互距離最小的一對(duì)點(diǎn)。出其

5、中相互距離最小的一對(duì)點(diǎn)。n此問(wèn)題的簡(jiǎn)單解法是，算出每個(gè)點(diǎn)與其它此問(wèn)題的簡(jiǎn)單解法是，算出每個(gè)點(diǎn)與其它n1 個(gè)點(diǎn)之個(gè)點(diǎn)之間的距離，再找出其中距離最小的一對(duì)點(diǎn)。這樣做的間的距離，再找出其中距離最小的一對(duì)點(diǎn)。這樣做的時(shí)間復(fù)雜性為時(shí)間復(fù)雜性為O(n2)。n下面用分治法構(gòu)造一個(gè)時(shí)間復(fù)雜性為下面用分治法構(gòu)造一個(gè)時(shí)間復(fù)雜性為O(nlogn)的算的算法。法。n為此我們先考慮一維的情況：為此我們先考慮一維的情況：在應(yīng)用中，在應(yīng)用中，常用諸如點(diǎn)、圓等簡(jiǎn)單的幾何對(duì)象代表現(xiàn)實(shí)世界中常用諸如點(diǎn)、圓等簡(jiǎn)單的幾何對(duì)象代表現(xiàn)實(shí)世界中的實(shí)體。的實(shí)體。在涉及這些幾何對(duì)象的問(wèn)題中，在涉及這些幾何對(duì)象的問(wèn)題中，常需要了解其鄰域中其他幾

6、何對(duì)象的信息。常需要了解其鄰域中其他幾何對(duì)象的信息。例如，在空中交通控制問(wèn)題中，例如，在空中交通控制問(wèn)題中，若將飛機(jī)作為空間中移動(dòng)的一個(gè)點(diǎn)來(lái)看待，若將飛機(jī)作為空間中移動(dòng)的一個(gè)點(diǎn)來(lái)看待，則具有最大碰撞危險(xiǎn)的則具有最大碰撞危險(xiǎn)的2架飛機(jī)，架飛機(jī)，就是這個(gè)空間中最接近的一對(duì)點(diǎn)。就是這個(gè)空間中最接近的一對(duì)點(diǎn)。這類問(wèn)題是計(jì)算幾何學(xué)中研究的基本問(wèn)題之一這類問(wèn)題是計(jì)算幾何學(xué)中研究的基本問(wèn)題之一。 一維最接近點(diǎn)對(duì)一維最接近點(diǎn)對(duì)n設(shè)設(shè)S為為x軸上軸上n個(gè)點(diǎn)的集合，求個(gè)點(diǎn)的集合，求S中最接近點(diǎn)對(duì)。中最接近點(diǎn)對(duì)。n假設(shè)用假設(shè)用x軸上某個(gè)點(diǎn)軸上某個(gè)點(diǎn)m劃分劃分S為為S1和和S2，使得，使得S1=xS | xm，S2=

7、xS | xm。n遞歸地在遞歸地在S1和和S2中找出其最接近點(diǎn)對(duì)中找出其最接近點(diǎn)對(duì)p1，p2和和q1，q2，并設(shè)，并設(shè)d = min|p1，p2|， |q1，q2|n易知，易知，S中最接近點(diǎn)對(duì)是中最接近點(diǎn)對(duì)是p1，p2或或q1，q2，或，或 p3，q3，這里，這里p3=maxS1，q3 =minS2。mS1S2p1p2p3q3q1q2一維最接近點(diǎn)對(duì)算法一維最接近點(diǎn)對(duì)算法nbool Cpair1(S, d)nn n = |S|;n if (n mn Cpair1(S1, d1); n Cpair1(S2, d2); /分別求分別求S1和和S2的最接近點(diǎn)對(duì)的最接近點(diǎn)對(duì)n p=maxS1; q =m

8、inS2; d = mimd1, d2, q p;n return true n一維最接近點(diǎn)對(duì)算法復(fù)雜性一維最接近點(diǎn)對(duì)算法復(fù)雜性n如果對(duì)如果對(duì)S的分割不平衡的話，最壞的情況是的分割不平衡的話，最壞的情況是S1僅含僅含一個(gè)點(diǎn)，這時(shí)算法的復(fù)雜性為一個(gè)點(diǎn)，這時(shí)算法的復(fù)雜性為O(n2)。n所以要采用所以要采用中位數(shù)中位數(shù)m來(lái)分割來(lái)分割S。n該算法的分割步驟和合并步驟總共耗時(shí)該算法的分割步驟和合并步驟總共耗時(shí)O(n)，因，因此算法耗時(shí)滿足遞歸方程此算法耗時(shí)滿足遞歸方程T(n) =O(1) n02T(n/2) + O(n) n4n解此遞歸方程可得解此遞歸方程可得T(n) = O(nlogn)。平面最接近點(diǎn)

9、對(duì)平面最接近點(diǎn)對(duì)n做一條直線做一條直線L：x=m，將，將S分割為分割為S1和和S2，其中，其中m為為所有點(diǎn)的所有點(diǎn)的x坐標(biāo)的中位數(shù)。遞歸地求得坐標(biāo)的中位數(shù)。遞歸地求得S1和和S2中的中的最小距離最小距離d1和和d2，令，令d=mind1，d2。LS1S2d1d2n但是但是S1和和S2之間的最小距離卻需要考察之間的最小距離卻需要考察S1和和S2 在在l兩側(cè)距離不超過(guò)兩側(cè)距離不超過(guò)d的區(qū)域的區(qū)域P1和和P2間的點(diǎn)對(duì)。間的點(diǎn)對(duì)。dP1dP2nP1和和P2間的點(diǎn)對(duì)均為最近點(diǎn)對(duì)間的點(diǎn)對(duì)均為最近點(diǎn)對(duì)的候選，最壞情況有的候選，最壞情況有n2/4個(gè)。個(gè)。n而實(shí)際上，對(duì)而實(shí)際上，對(duì)P1中的任意一點(diǎn)，中的任意一點(diǎn)

10、，最多只需要考察最多只需要考察P2中的中的6個(gè)點(diǎn)。個(gè)點(diǎn)。最多只需要考察最多只需要考察6 6個(gè)點(diǎn)個(gè)點(diǎn)n考慮考慮P1中的任意一點(diǎn)中的任意一點(diǎn)p，它若與，它若與P2中的點(diǎn)中的點(diǎn)q構(gòu)成最構(gòu)成最接近點(diǎn)對(duì)，則其距離必定小于接近點(diǎn)對(duì)，則其距離必定小于d。這樣的點(diǎn)必定。這樣的點(diǎn)必定落在一個(gè)落在一個(gè)d2d的矩形的矩形R內(nèi)：內(nèi)：LP1P2pddR 在矩形R中最多有6個(gè)點(diǎn)。 不然的話，可以將矩形不然的話，可以將矩形R分成分成6個(gè)個(gè)(d/2)(2d/3)個(gè)小矩形，個(gè)小矩形， 每個(gè)小矩形對(duì)角線的長(zhǎng)度為每個(gè)小矩形對(duì)角線的長(zhǎng)度為5d/6。(d/2)2+(2d/3)2=25d2/36 若若R中有中有6個(gè)以上的點(diǎn)，則個(gè)以上的點(diǎn)

11、，則必有兩點(diǎn)必有兩點(diǎn)u、v在同一小矩形在同一小矩形內(nèi)，內(nèi)， 于是于是|uv|5d/6。矛盾。矛盾。（鴿舍原理鴿舍原理） 所以所以R中至多有中至多有6個(gè)點(diǎn)，即對(duì)個(gè)點(diǎn)，即對(duì)P1中的每個(gè)點(diǎn)至多只需要考中的每個(gè)點(diǎn)至多只需要考察察P2中的中的6個(gè)點(diǎn)就可以了。個(gè)點(diǎn)就可以了。 分別將分別將P1和和P2中的點(diǎn)按中的點(diǎn)按y坐標(biāo)坐標(biāo)排序；再對(duì)排序；再對(duì)P1中的每個(gè)點(diǎn)中的每個(gè)點(diǎn)p，考察考察P2中中y坐標(biāo)在坐標(biāo)在y(p)d范圍范圍內(nèi)的點(diǎn)內(nèi)的點(diǎn)(最多最多6個(gè)個(gè))。平面最接近點(diǎn)對(duì)的算法平面最接近點(diǎn)對(duì)的算法nbool Cpair2(S, d)n n = |S|;n if (n2) d = ; return falsen m

12、 = S中各點(diǎn)x坐標(biāo)的中位數(shù)；構(gòu)造S1和S2； n Cpair2(S1, d1); Cpair2(S2, d2); dm=min(d1, d2)n 構(gòu)造P1和P2；n /P1=p|mdmx(p)m, P2=q|mx(q)m+dmn 將P1和P2中的點(diǎn)按y坐標(biāo)值排序；n 依次掃描P1中點(diǎn)u并計(jì)算u與P2中y坐標(biāo)在y(u)dm范圍內(nèi)的點(diǎn)(最多6個(gè))；設(shè)dl是這樣找到的最小距離；n d = min(dm, dl);n return true 最接近點(diǎn)對(duì)算法的復(fù)雜性最接近點(diǎn)對(duì)算法的復(fù)雜性n則在算法中：則在算法中：n計(jì)算中位數(shù)和計(jì)算中位數(shù)和min需時(shí)為常數(shù)。需時(shí)為常數(shù)。n將將S分割為分割為S1和和S2需

13、時(shí)為需時(shí)為O(n)。n在排序后的在排序后的P1和和P2中找最小距離中找最小距離dl需時(shí)為需時(shí)為O(n)。n對(duì)對(duì)P1和和P2排序在最壞情況下需時(shí)排序在最壞情況下需時(shí)O(nlogn)，這，這不符合要求。不符合要求。n由此易知遞歸需時(shí)為由此易知遞歸需時(shí)為O(nlogn)，預(yù)排序需時(shí)為，預(yù)排序需時(shí)為O(nlogn)，因而整個(gè)算法需時(shí)為，因而整個(gè)算法需時(shí)為O(nlogn)。n若在整個(gè)算法開始之前對(duì)各點(diǎn)的若在整個(gè)算法開始之前對(duì)各點(diǎn)的y坐標(biāo)進(jìn)行一坐標(biāo)進(jìn)行一次預(yù)排序，則在遞歸中就無(wú)須再排序，只要對(duì)次預(yù)排序，則在遞歸中就無(wú)須再排序，只要對(duì)P1或或P2進(jìn)行線性掃描即可，需時(shí)仍為進(jìn)行線性掃描即可，需時(shí)仍為O(n)。

14、減治與遞歸減治與遞歸俄羅斯農(nóng)夫法俄羅斯農(nóng)夫法假定需要求的乘積，顯然有假定需要求的乘積，顯然有 2 ,2-12,2mnmm nmnnm是偶數(shù)是奇數(shù)以以 作為算法的終止條件作為算法的終止條件。1 nn僅減小問(wèn)題僅減小問(wèn)題規(guī)模規(guī)模例如，要求例如，要求3939和和7979的乘積，算法的運(yùn)行過(guò)程如下：的乘積，算法的運(yùn)行過(guò)程如下： 39 79 19 158 +79 9 316 +1584 632 +316 2 1264 1 2528 39797915831625283081對(duì)整數(shù)的乘法計(jì)算是很有實(shí)際意義對(duì)整數(shù)的乘法計(jì)算是很有實(shí)際意義39*79=19*158+79 =9*316+158+79=？減治與遞歸減

15、治與遞歸通過(guò)建立原問(wèn)題實(shí)例的解和同樣問(wèn)題較小實(shí)例的解的關(guān)系，通過(guò)建立原問(wèn)題實(shí)例的解和同樣問(wèn)題較小實(shí)例的解的關(guān)系，并利用這種關(guān)系，從頂而下（遞歸地）或從底而上（非遞歸并利用這種關(guān)系，從頂而下（遞歸地）或從底而上（非遞歸地）解決問(wèn)題。地）解決問(wèn)題。 規(guī)模逐步減小，但規(guī)模逐步減小，但問(wèn)題不分解問(wèn)題不分解(1) 消去一個(gè)常量：每次算法迭代總是從原問(wèn)題規(guī)模中減消去一個(gè)常量：每次算法迭代總是從原問(wèn)題規(guī)模中減去一個(gè)規(guī)模相同的常量（一般為去一個(gè)規(guī)模相同的常量（一般為1）。）。插入排序?qū)儆谠摲N插入排序?qū)儆谠摲N方法。方法。三種常見形式：三種常見形式：(2) 減去一個(gè)常數(shù)因子：從原問(wèn)題的規(guī)模中減去一個(gè)相同的減去一個(gè)

16、常數(shù)因子：從原問(wèn)題的規(guī)模中減去一個(gè)相同的常數(shù)因子，該因子一般是常數(shù)因子，該因子一般是2。如。如俄羅斯農(nóng)夫法俄羅斯農(nóng)夫法(3) 減去可變規(guī)模：規(guī)模減小的模式都是不同的。減去可變規(guī)模：規(guī)模減小的模式都是不同的。如計(jì)算計(jì)算最大公約數(shù)的輾轉(zhuǎn)相除法。最大公約數(shù)的輾轉(zhuǎn)相除法。分治法小結(jié)分治法小結(jié)1 分治法的特點(diǎn)分治法的特點(diǎn)2 可利用分治法求解得問(wèn)題的特點(diǎn)可利用分治法求解得問(wèn)題的特點(diǎn)3 分治法的算法設(shè)計(jì)分治法的算法設(shè)計(jì)遞歸算法遞歸算法4 分治法的分治法的時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度分析并行算法并行算法替換法（分治替換法（分治1）思考：思考：1 分治策略一定包含遞歸嗎？如果是，請(qǐng)解釋，如果不是，給分治策略一定包含

17、遞歸嗎？如果是，請(qǐng)解釋，如果不是，給出一個(gè)不包含遞歸的分治例子，并闡述這種分治和包含遞歸出一個(gè)不包含遞歸的分治例子，并闡述這種分治和包含遞歸的分治的不同。的分治的不同。2 我們通常說(shuō)分治包含遞歸，但是否遞歸也包含分治呢？為什我們通常說(shuō)分治包含遞歸，但是否遞歸也包含分治呢？為什么么?哈工大2003春季1算法分析的目的是( ) A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法的輸入/輸出關(guān)系C.分析算法的效率以求改進(jìn) D.分析算法的易讀性6深度為5的二元樹至多有( )個(gè)結(jié)點(diǎn)。 A.16 B.32 C 31 D.10 1. 算法的計(jì)算量的大小稱為計(jì)算的（ ）?！颈本┼]電大學(xué)2000 二、3 （20/8分）】

18、A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度2. 算法的時(shí)間復(fù)雜度取決于（ ）【中科院計(jì)算所 1998 二、1 （2分）】A問(wèn)題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B3.計(jì)算機(jī)算法指的是（1），它必須具備（2） 這三個(gè)特性。(1) A計(jì)算方法 B. 排序方法 C. 解決問(wèn)題的步驟序列 D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴(kuò)充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 【南京理工大學(xué) 1999 一、1（2分） 【武漢交通科技大學(xué) 1996 一、1（ 4分）】4一個(gè)算法應(yīng)該是（ ）?！局猩酱髮W(xué) 1998 二、1（2分）】 A程序

19、B問(wèn)題求解步驟的描述 C要滿足五個(gè)基本特性 DA和C. 5. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（ ）【南京理工大學(xué) 2000 一、1（1.5分）】A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問(wèn)題的算法同為該問(wèn)題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的6. 下面說(shuō)法錯(cuò)誤的是（ ）【南京理工大學(xué) 2000 一、2 （1.5分）】 (1）算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法 （3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界 （4）同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越

20、高，執(zhí)行效率就越低A(1) B.(1),(2) C.(1),(4) D.(3)11在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（ ）【北京工商大學(xué) 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 12.下面程序段的時(shí)間復(fù)雜度是（ ）2014年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)專業(yè)基礎(chǔ)綜合Count=0;for(i=1;i=n;i*=2) for(j=1;j=n;j+) count+ ;1. 算法的計(jì)算量的大小稱為計(jì)算的（ ）?！颈本┼]電大學(xué)2000 二、3 （20/8分）】A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度2. 算法的時(shí)間復(fù)雜度取決于（ ）【中科院計(jì)算所 1998 二、1 （2分）】A問(wèn)題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C