算法設(shè)計(jì)與分析-2

1、 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn):理解遞歸的概念。掌握設(shè)計(jì)有效算法的分治策略。通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。（1）二分搜索技術(shù)； （2）大整數(shù)乘法；（3）Strassen矩陣乘法；（4）棋盤(pán)覆蓋；(（5）合并排序和快速排序；)（6）線性時(shí)間選擇；（7）最接近點(diǎn)對(duì)問(wèn)題；（8）循環(huán)賽日程表減治法算法功能、性能考慮高性能計(jì)算(HPC)/超級(jí)計(jì)算機(jī)系統(tǒng)并行算法與超級(jí)計(jì)算nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設(shè)計(jì)思

2、想：將一個(gè)難以直接解決的大問(wèn)題，分治法的設(shè)計(jì)思想：將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。分而治之。對(duì)程序設(shè)計(jì)的影響：對(duì)程序設(shè)計(jì)的影響： 多核、多處理機(jī)上的多線程編程多核、多處理機(jī)上的多線程編程 multithread programmingnT(n/2)T(n/2)T(n/2)T(n/2)T(n)= n將大問(wèn)題分解為k個(gè)子問(wèn)題，對(duì)這k個(gè)子問(wèn)題分別求解。n對(duì)這k個(gè)子問(wèn)題分別求解時(shí)，如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T

3、(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n各小規(guī)模的子問(wèn)題獨(dú)立求解n將求出的子問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法的前提n大問(wèn)題分解為子問(wèn)題后，各個(gè)子問(wèn)題可以獨(dú)立（并

4、行、同時(shí)并行、同時(shí)）求解，相互間無(wú)直接交互、依賴(lài)關(guān)系n子問(wèn)題解的（簡(jiǎn)單）合并，可以得到原問(wèn)題的解2.1 n遞歸函數(shù)遞歸函數(shù): 用函數(shù)自身給出定義的函數(shù)。n遞歸算法遞歸算法:直接或間接地調(diào)用自身的算法n分治vs 遞歸 由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。n分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。 遞歸還可以用于描述以自相似方法重復(fù)事物的過(guò)程，e.g.兩面鏡子相互之間近似平行時(shí)，鏡

5、中嵌套的圖像是以無(wú)限遞歸的形式出現(xiàn)的 例例1 階乘函數(shù)階乘函數(shù)階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊界條件邊界條件遞歸方程遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。例例2 Fibonacci數(shù)列數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱(chēng)為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件邊界條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n 1時(shí)，perm(R)由： (r1)perm(

6、R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 nE.g. perm(1,2,3): 1 perm(2,3) 123, 132 2 perm(1,3) 213, 231 3 perm(1,2) 312, 321 (1)1( )(1)( )1OnT nnT nf nn非線性！例例5 5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題 將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1，k1。 正整數(shù)n的這種表示稱(chēng)為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。 例如正整數(shù)6有如下11種不同的劃分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2

7、+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。e.g. 6=1+1+1+1+1+1(2) q(n,m)=q(n,n), mn; e.g. q(6, 7)=q(6, 6) 最大加數(shù)n1=m實(shí)際上不能大于n,因此，q(1,m)=1。(1) q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式，即 n=1+1+1 前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為正整數(shù)n的劃分的數(shù)目，則難以找到遞歸關(guān)系。 因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。e.g. q(6

8、,3) 可以建立q(n,m)的如下遞歸關(guān)系。(3) !q(n,n)=1+q(n,n-1); /*問(wèn)題規(guī)模中第2變量減小 e.g. q(6,6) = 1 + q(6,5) 正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。q(6,5)(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; e.g. n=6, m=4 q(6, 4) = q(6,3) + q(2, 4) = q(6,3) + q(2, 2)正整數(shù)n的最大加數(shù)n1不大于

9、m的劃分的數(shù)目等于: i)n的最大加數(shù)n1=m-1的劃分?jǐn)?shù)目 + ii) n-m的最大加數(shù)n1=m 的劃分?jǐn)?shù) 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。q(6,4)=2+7q(6,3)=7個(gè)數(shù)2=q(2,4)=q(2,2)2;1+111, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq建立q(n,m)的如下遞歸關(guān)系: 正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)e.g.p(6)=q(6,6) 例例6 Hanoi塔問(wèn)題塔問(wèn)題設(shè)a,b,c是3個(gè)塔座。開(kāi)

10、始時(shí)，在塔座a上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,n, 現(xiàn)要求將塔座a上的這一疊圓盤(pán)移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則3：在滿(mǎn)足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至a,b,c中任一塔座上。在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤(pán)從塔座a直接移至塔座b上即可。當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則

11、從塔座a移至塔座c，然后，將剩下的最大圓盤(pán)從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見(jiàn)，n個(gè)圓盤(pán)的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤(pán)的移動(dòng)問(wèn)題，這又可以遞歸地用上述方法來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法如下。n-1void hanoi(int n, int a, int b, int c)/*將A上n個(gè)盤(pán)子， 借助C，移到B if (n 0) hanoi(n-1, a, c, b); /*將A上的n-1個(gè)盤(pán)子，借助B，移到C move(a,b); /*將A上剩余的最大/最底層盤(pán)子直接移到B hanoi(n-1, c, b, a); /*

12、將C上的n-1個(gè)盤(pán)子， 借助A，移到B上 abc(1)(2)(3)(1)1( )2 (1)(1)1OnT nT nOnT(1)=1, T(2)=3, T(3)=7T(n)=2n - 1 n=64, T(n)=?!優(yōu)點(diǎn)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。非遞歸算法要多。

13、解決方法：解決方法：在遞歸算法中消除遞歸調(diào)用，使其在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。轉(zhuǎn)化為非遞歸算法。1 1、采用一個(gè)用戶(hù)定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)、采用一個(gè)用戶(hù)定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。優(yōu)化效果不明顯。2 2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3 3、通過(guò)、通過(guò)變換能變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善

14、，后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。但其適用范圍有限。n該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決:n該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì). e.g. 反例，反例，hanoi(n, a,b,c) 因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿(mǎn)足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿(mǎn)足的，此特征反映了遞歸思想的應(yīng)用n利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該利用該問(wèn)題分解出的子問(wèn)題的解可以

15、合并為該問(wèn)題的解；問(wèn)題的解；n該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。即子問(wèn)題之間不包含公共的子問(wèn)題。 能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法貪心算法或動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃。反例：兩點(diǎn)間最短路徑這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃較好。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問(wèn)

16、題 divide P into smaller subinstances P1,P2,.,Pk；/分解問(wèn)題 for (i=1,i=k,i+) /串行、并行串行、并行遞歸地解各子問(wèn)題 yi=divide-and-conquer(Pi); return merge(y1,.,yk); /將各子問(wèn)題的解合并為原問(wèn)題的解 人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。即將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。 這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平平衡衡(balancing)子問(wèn)題子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。E.g. 正例：二分搜

17、索、合并排序 反例：Hanoi塔， 2個(gè)子問(wèn)題：n-1個(gè)盤(pán)、底層1個(gè)最大盤(pán)nT(n)=n/mn/mn/mn/m123k.采用分治法，將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為n/m的子問(wèn)題去解。j=0, 原問(wèn)題j=1原問(wèn)題/子問(wèn)題所處層次: j, j=0,1,2, logmn-1第j層原問(wèn)題/子問(wèn)題的規(guī)模： n/mj第j層原問(wèn)題/子問(wèn)題的總數(shù)： kj設(shè)分解閥值n0=1，且解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。 再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f(n)個(gè)單位時(shí)間。 用T(n)表示該分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有：11)()/() 1 ()(nn

18、nfmnkTOnT通過(guò)迭代法求得方程的解：log1log0( )( /)nmkjjmjT nnk f n mK個(gè)子問(wèn)題串行求解代價(jià)各層原問(wèn)題子問(wèn)題分解、合并代價(jià)累加第j層子問(wèn)題總數(shù)第j層的1個(gè)子問(wèn)題分解合并代價(jià)第j層子問(wèn)題規(guī)模1. m n 分解后全部子問(wèn)題總規(guī)模 原問(wèn)題規(guī)模 T(n)復(fù)雜性較大 e.g. 矩陣乘，k=7, m=2，分解成7個(gè)子問(wèn)題，每個(gè)子問(wèn)題規(guī)模是原問(wèn)題的1/2, 2. m=k: k*(n/m)=n, 分解后全部子問(wèn)題總規(guī)模 = 原問(wèn)題規(guī)模 e.g. 合并排序，k=2, m=2，O(nlogn) log1log0( )( /)nmkjjmjT nnk f n mlogkmnn2

19、loglog 72.81kmnnnlogkmnn3. mk: k*(n/m)n, 分解后全部子問(wèn)題總規(guī)模原問(wèn)題規(guī)模 e.g. 二分搜索，m=2, k=1, O(logn)注意注意： 遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(mén)(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。 通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)T(mi+1)。 logkmnn給定已按升序排好序的給定已按升序排好序的n個(gè)元素個(gè)元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個(gè)元素中找個(gè)元素中找出一特定元素出一特定元素x。分析：分析：該問(wèn)題的規(guī)?？s小到一定

20、的程度就可以容易地解決：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決：分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿(mǎn)足分治法的第一個(gè)適用條件該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分析：比較x和a的中間元素amid， 1）若x=amid，則x在L中的位置就是mid； 2）如果xai，同理我們只要在amid的后面查找x即可。 因此，無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。這就說(shuō)明了此問(wèn)題滿(mǎn)

21、足分治法的第二個(gè)和第三個(gè)適用條件 子問(wèn)題規(guī)模為原問(wèn)題規(guī)模1/2, 只需求解1個(gè)子問(wèn)題 m=2, k=1 分解出的各個(gè)子問(wèn)題是相互獨(dú)立的分解出的各個(gè)子問(wèn)題是相互獨(dú)立的 分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿(mǎn)足分治法的第四個(gè)適用條件。 給定已按升序排好序的給定已按升序排好序的n個(gè)元素個(gè)元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個(gè)元素中找個(gè)元素中找出一特定元素出一特定元素x。二分搜索算法二分搜索算法：template int BinarySearch(Type a, const Type& x, int l, int r) while (r =

22、 l) int m = (l+r)/2; if (x = am) return m; if (x 0時(shí)，將2k2k棋盤(pán)分割為4個(gè)2k-12k-1 子棋盤(pán)(a)所示。 特殊方格必位于4個(gè)較小子棋盤(pán)之一中，其余3個(gè)子棋盤(pán)中無(wú)特殊方格，即4個(gè)子問(wèn)題出現(xiàn)差異。 為了將這3個(gè)無(wú)特殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤(pán)的會(huì)合處，如 (b)所示，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模、完全相同的棋盤(pán)覆蓋子問(wèn)題。 遞歸地使用這種分割，直至棋盤(pán)簡(jiǎn)化為棋盤(pán)11。 void chessBoard(int tr, int tc, int dr, int dc, int size) tr: 棋盤(pán)左上

23、角方格行號(hào)， tc:棋盤(pán)左上角方格列號(hào) dr: 特殊方格所在行號(hào)， dc: 特殊方格所在列號(hào) size：描述棋盤(pán)大小的參數(shù) if (size = 1) return; /直接用1個(gè)L型骨牌 int t = tile+, / L型骨牌號(hào) s = size/2; / 分割棋盤(pán) 1./ 覆蓋左上角子棋盤(pán) if (dr tr + s & dc tc + s) / 特殊方格在此棋盤(pán)中 chessBoard(tr, tc, dr, dc, s); else / 此子棋盤(pán)中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋右下角 boardtr + s - 1tc + s - 1 = t; / 覆蓋其余方格 c

24、hessBoard(tr, tc, tr+s-1, tc+s-1, s); 2./ 覆蓋右上角子棋盤(pán) if (dr = tc + s) / 特殊方格在此棋盤(pán)中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤(pán)中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋左下角 boardtr + s - 1tc + s = t; / 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); 即k=1 3. / 覆蓋左下角子棋盤(pán) if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格

25、在此棋盤(pán)中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 號(hào)L型骨牌覆蓋左上角 boardtr + stc + s = t; / 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 注意事項(xiàng)：n將大的棋盤(pán)一分為四，在4個(gè)子棋盤(pán)的交匯處，添加L型骨牌，這4個(gè)子棋盤(pán)的結(jié)構(gòu)布局不一定相同 （1）相同結(jié)構(gòu)布局，添加L型骨牌后，特殊方格均在在子棋盤(pán)頂點(diǎn)。 對(duì)4個(gè)子問(wèn)題，采用相同的求解步驟(2) 結(jié)構(gòu)布局不相同，特殊方格不在子棋盤(pán)頂點(diǎn)。添加L型骨牌后，4個(gè)子問(wèn)題結(jié)構(gòu)不一樣。 對(duì)各個(gè)子問(wèn)題繼續(xù)劃分、添加L型骨牌，直到特殊方

26、格或L型骨牌方格均在子棋盤(pán)的頂點(diǎn)復(fù)雜度分析復(fù)雜度分析T(n)=O(4k) = O(22k) = O(2k2) = O(2k)2)= O(n2)漸進(jìn)意義下的最優(yōu)算法 (n=2k)(1)1( )4 (1)(1)1OkT kT kOkO(1) : 在原問(wèn)題中，下述2步所花時(shí)間 1）判斷特殊格子所在位置 2）在中心點(diǎn)處添加L型骨牌基本思想：基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序; 將排好序的子集合合并成為所要求的排好序的集合。 void MergeSort(Type a, int left, int right) if (leftright) /*至少有2個(gè)元素

27、int i=(left+right)/2; /*取中點(diǎn) mergeSort(a, left, i); /*左子問(wèn)題求解 mergeSort(a, i+1, right); /*右子問(wèn)題求解 merge(a, b, left, i, right); /合并到數(shù)組b, 關(guān)鍵 ! copy(a, b, left, right); /復(fù)制回?cái)?shù)組a ileftrighta0:n-1 k=2, m=2729412346789輸入序列輸出序列3861729438617 29 4722 7944 9247913683 86 1383 8611 6分解合并算法mergeSort的遞歸過(guò)程可以消去。初始序列49

28、38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97復(fù)雜度分析復(fù)雜度分析T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法Why？11)()2/(2) 1 ()(nnnOnTOnTlo g1lo g0lo g12lo g220lo g1lo g1220022 ,2 ,()()(/)22*1* lo g()(lg)(lo g)nmkjjmjnjjjnnjjkmfnc nTnnkfnmc nnnc nnc nnc nnOnOnnOnn&最壞時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：O(n

29、logn)&平均時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)特點(diǎn)：分解簡(jiǎn)單，合并復(fù)雜templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對(duì)左半段排序 QuickSort (a,q+1,r); /對(duì)右半段排序 原理：對(duì)輸入的子數(shù)組ap:r， step1. 分解：按照一定規(guī)則，選擇aq, 以 aq為基準(zhǔn)元素，將劃分為三段 ap:q-1, aq, aq+1, r，使得ap:q-1中的元素均小于aq, aq+1

30、,r中的元素 均大于aq step2. 遞歸求解： 遞歸調(diào)用快速排序算法，對(duì)ap:q-1和aq+1, r分別排序 step3. 合并：不需做任何計(jì)算，因?yàn)榻?jīng)上2步后， ap:r已經(jīng)排好序初始序列6, 7, 5, 2, 5, 8分解后5, 2, 5 6 7, 8Partition： aparaqtemplateint Partition (Type a, int p, int r) int i = p, j = r + 1; Type x=ap; /*第1個(gè)元素 / 將 x的元素交換到右邊區(qū)域 while (true) while (a+i x); if (i = j) break; Swap(

31、ai, aj); ap = aj; aj = x; return j;初始序列6, 7, 5, 2, 5, 8j-;ji5, 7, 5, 2, 6, 8i+;ji5, 6, 5, 2, 7, 8j-;ji5, 2, 5, 6, 7, 8i+;ji完成6, 7, 5, 2, 5, 85, 2, 5 6 7, 8在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。xtemplateint RandomizedPartition (Type a, int p, int

32、r) int i = Random(p,r); Swap(ai, ap); return Partition (a, p, r); 與劃分元素aq密切相關(guān)：算法性能取決于劃分的對(duì)稱(chēng)性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法： 在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱(chēng)的。&最壞時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：O(n2)&平均時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)或或O(logn)最壞時(shí)間復(fù)雜性n最

33、壞情況發(fā)生在劃分產(chǎn)生的2個(gè)子序列中，1個(gè)有n-1個(gè)元素，而另一個(gè)有0個(gè)元素n此時(shí)復(fù)雜度 T(n) = T(n-1) + O(n) = T(n-2) + O(n) + O(n-1) = O(n2)6, 7, 5, 2, 5, 8： 2 6, 7, 5, 5, 8 x最好時(shí)間復(fù)雜性n最好情況發(fā)生在劃分產(chǎn)生的2個(gè)子序列幾乎是等長(zhǎng)的n此時(shí)復(fù)雜度 T(n) = 2T(n/2) + (n) = (nlogn)2, 7, 5, 6, 5, 8: 2,5,5 6 7,8x平均時(shí)間復(fù)雜性n計(jì)算平均時(shí)間復(fù)雜性時(shí)，要考慮各種可能的輸入：由n個(gè)值組成的序列 X=a1, a2, , ann快速排序只與要排序的序列值的相

34、對(duì)順序有關(guān)，與具體值無(wú)關(guān)。 e.g X1=1, 5, 3, 2, 9, 8, 4 vs X2=10, 50, 30, 20, 90, 80, 40n因此，假設(shè)序列中各值是不相同的n為簡(jiǎn)化分析，同時(shí)兼顧各種可能的輸入情況，以序列X中n個(gè)元素的各種可能排列(共有n!個(gè))作為算法的輸入，并且其機(jī)會(huì)是均等的輸入的隨機(jī)性n將輸入序列看作是隨機(jī)的，保證了X中每個(gè)值被選為分割點(diǎn)的概率是相等的，均為1/n 分割點(diǎn)的隨機(jī)、等概率n假設(shè)X中第q小的值被選為分割點(diǎn)，原問(wèn)題被分割成2個(gè)子問(wèn)題：1個(gè)規(guī)模為q-1，另一個(gè)為n-q 1, 5, 3, 2, 9, 8, 4 1, 2, 5, 3, 9, 8, 4 , n=7,

35、 q=21111111()(1(1)()1(1)()1(1)()1()(1)()12(1)1.(1)(lo g)(lg)nqnqnnqqnqnqTnnTqTnqnTqTnqnnTqTnqTnTqTnqnnTqnnnnnn 由 于 :對(duì)分割點(diǎn)之外的其它n-1個(gè)點(diǎn)掃描、比較，將序列分為3部分給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1kn，要求找出這n個(gè)元素中第k小的元素 n個(gè)元素存放在a0: n-1中 k=1: 求最小元素 k=n: 求最大元素 k=(n+1)/2, 求中位數(shù)E.g. 4, 2, 5, 6, 7, 1, 9, 0, 3 n=9 k=4隨機(jī)選擇算法 原理：模仿遞歸劃分排序算法，對(duì)輸入數(shù)據(jù)

36、進(jìn)行劃分排序隨機(jī)選擇算法為求a0 : n-1中的第k小元素，執(zhí)行RandomizedSelect(a, 0, n-1, k)原理：模仿遞歸劃分排序算法，利用上一節(jié)的隨機(jī)劃分算法RandomizedPartition，對(duì)輸入數(shù)據(jù)進(jìn)行劃分排序RandomizedPartition(a,p,r)：ap:r被劃分為ap:i和ai+1,r，使得ap:i中的每個(gè)元素不大于ai+1,r中的每個(gè)元素.劃分方法：用最右端元素為基準(zhǔn)，劃分為2部分， 基準(zhǔn)元素仍然位于ai+1,r E.g. 4, 2, 5, 6, 7, 1, 9, 0, 3 ap,i =2,1,0 ai+1,r =4,5,6,7,9,3456793

37、aparai210ai+1templateType RandomizedSelect( Type a, int p, int r, int k) if (p=r) return ap;/*只有1個(gè)元素 int i=RandomizedPartition(a,p,r), /*劃分為2部分 j=i-p+1; /*左端小元素個(gè)數(shù)，e.g. j=4 if (k=j) /* e.g. k=2， 第2小的元素1 return RandomizedSelect(a,p,i,k); /*在左半部分查找 else return RandomizedSelect(a,i+1,r,k-j); /* e.g. k=5

38、 第5小的元素4 /*在右半部分查找n算法randomizedSelect可以在O(n)平均(當(dāng)k=1,2,3,n) 時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素 說(shuō)明：比排序算法的復(fù)雜性?。Why： 減治法，不需完全排序n在最壞情況下，算法randomizedSelect需要O(n2) 關(guān)鍵：如何降低最壞復(fù)雜性？n為降低最壞復(fù)雜性，要求盡可能保證劃分后的2個(gè)子集大小接近，不要相差過(guò)大不平衡如果還是以a0: n-1的最右端元素為基準(zhǔn)，有可能非平衡反例： ap,r =4, 2, 5, 6, 7, 1, 9, 0, 10 ap,i =4, 2, 5, 6, 7, 1, 9, 0 ai+1,r =10 為

39、降低最壞情況復(fù)雜性，需要：在線性時(shí)間內(nèi)找到為降低最壞情況復(fù)雜性，需要：在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的2個(gè)子數(shù)組的長(zhǎng)度都至多至多!為原數(shù)組長(zhǎng)度的倍(01是某個(gè)正常數(shù))，那么產(chǎn)生的子數(shù)組的長(zhǎng)度至少至少縮短(1- )倍，就可以在最壞情況下在最壞情況下用O(n)時(shí)間完成選擇任務(wù)子問(wèn)題平衡 例如，若=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少至少縮短1/10。 所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿(mǎn)足遞歸式: T(n)T(9n/10) + O(n) ，經(jīng)遞推求解，可得T(n)=O(n)劃分基準(zhǔn)尋找方法：1）將n個(gè)輸入元素劃分成m=n/5個(gè)組，每組5個(gè)元素

40、，只可能有一個(gè)組不是5個(gè)元素 O(n)j=1j=2j=3j=4j=5j=6j=7n=33, m=7, j=1,2,72）用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共m=n/5個(gè) 復(fù)雜性n/5 * 5lg53）遞歸調(diào)用select來(lái)找出這n/5個(gè)元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。各組中位數(shù)組1組2組j中位數(shù)的中位數(shù) 設(shè)a0: n-1所有元素互不相同。找出的基準(zhǔn)滿(mǎn)足要求： 找出的基準(zhǔn)x至少比a0: n-1 中的3n/10-1個(gè)元素大1)在m=n/5個(gè)組中，至少有m/2個(gè)組的中位數(shù)基準(zhǔn)x，有m/2-1個(gè)組的中位數(shù)基準(zhǔn)x-x所在

41、組之前的m/2-1個(gè)組， x所在組， x所在組之后的m/2-1個(gè)組 x所在組之前的m/2-1個(gè)組的中位數(shù)均小于x2) 對(duì)x所在組之前的m/2-1個(gè)組，在每組中，均有2個(gè)元素小于本組中位數(shù)，而本組中位數(shù)x，所以每組共有有3個(gè)元素小于x3) 由1)，2)知，在x所在組之前的m/2-1個(gè)組中，共有3*(m/2-1)個(gè)元素小于x4) 對(duì)x所在組，有2個(gè)元素x因此，共有3*(m/2-1)+2=3m/2-1=3n/10-1個(gè)元素小于x 同理，找出的基準(zhǔn)x也至少比3n/10-1個(gè)元素小。 假設(shè)：要求劃分后的2個(gè)子數(shù)組長(zhǎng)度至少縮減1/4, 當(dāng)n20時(shí)， 3n/10 -1 n/4, 所以按此基準(zhǔn)劃分所得的2個(gè)子

42、數(shù)組的長(zhǎng)度都至少縮短1/4。劃分基準(zhǔn)尋找方法：1）將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素 O(n)2）用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè) n/5 * 5lg53）遞歸調(diào)用select來(lái)找出這n/5個(gè)元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。各組中位數(shù)組1組2組j中位數(shù)的中位數(shù)原書(shū)PPT，有問(wèn)題 設(shè)a0: n-1所有元素互不相同。找出的基準(zhǔn)滿(mǎn)足要求： 找出的基準(zhǔn)x至少比3(n-5)/10個(gè)元素大，因?yàn)樵诿恳唤M中有2個(gè)元素小于本組的中位數(shù)，而n/5個(gè)中位數(shù)中又有(n-5)/10？個(gè)

43、小于基準(zhǔn)x。 同理，找出的基準(zhǔn)x也至少比3(n-5)/10個(gè)元素小。 而當(dāng)n75？時(shí)，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至少縮短1/4。原書(shū)PPT，有問(wèn)題Type Select(Type a, int p, int r, int k) if (r-p20) 用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組ap:r排序; return ap+k-1; ; for ( int i = 0; i=(r-p-4)/5; i+ ) 將ap+5*i至ap+5*i+4的第3小元素 與ap+i交換位置; /找中位數(shù)的中位數(shù)，r-p-4即上面所說(shuō)的n-5 Type x = Select(a, p, p+(

44、r-p-4)/5, (r-p-4)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j);原書(shū)為75，有問(wèn)題復(fù)雜度分析復(fù)雜度分析T(n)=O(n)7575)4/3()5/()(21nnnTnTnCCnT ？，有問(wèn)題？，有問(wèn)題 上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。 這2點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和n/5+3n/4=19n/20=n，01。 這是使T(n)=O(n)的關(guān)鍵之處。 當(dāng)然，除了5和75之

45、外，還有其他選擇。給定平面上n個(gè)點(diǎn)的集合S，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。 u先考慮一維一維的情形。 此時(shí)，S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù) x1,x2,xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。假設(shè)用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2 ，基于平衡平衡子問(wèn)題子問(wèn)題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)(?有問(wèn)題)來(lái)作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對(duì)p1,p2和q1,q2，并設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點(diǎn)對(duì)或者是p1,p2，或者是q1,q2，或者是某個(gè)跨段的p3,q3，其中p3S1且q3S2。能否在線性時(shí)間內(nèi)

46、找到能否在線性時(shí)間內(nèi)找到p3,q3？說(shuō)明： “用S中各點(diǎn)坐標(biāo)的中位數(shù)來(lái)作分割點(diǎn)” 有問(wèn)題！在上圖中，如果m是S的中位數(shù)，則m包括在點(diǎn)集S中，即m包括在S1或S2中， 跨段點(diǎn)對(duì)(p3,q3)間距離(p3,m)間距離、 (m,q3)間距離 (p3,q3)不可能是最短點(diǎn)對(duì)！ 所以：如果選取m為中位數(shù)，算法后續(xù)步驟中不是考察跨段點(diǎn)對(duì)(p3,q3)，而是考察比較:1)段p1,m內(nèi)最短點(diǎn)對(duì), e.g.(p1,q1)2)段(m,q2內(nèi)最短點(diǎn)對(duì), e.g.(q1,q2)3)點(diǎn)m與段(m,q2內(nèi)最右端點(diǎn)q3組成的點(diǎn)對(duì)(m,q3)原書(shū)PPT，有問(wèn)題因此，參照上圖，正確的劃分方法是 1) 求出S中第n/2 小、第(

47、n/2 +1)小的p3,q3 2) 取m=(p3+q3)/2u如果S的最接近點(diǎn)對(duì)是跨段的p3,q3，即|p3-q3|d，則p3、q3兩者與m的距離均不超過(guò)d，即: |p3-m|=| p3-q3|d, |q3-m|=| q3-p3|0個(gè)點(diǎn)；d：最短距離1) if n=1 d=; return false /* O(1) if n=2 d=distance(p1,p2); return /* O(1)2) m=S中第n/2 小、第(n/2 +1)小的點(diǎn)的坐標(biāo)平均值 /*用線性時(shí)間選擇算法，O(n)3) 構(gòu)造S1、S2: /*問(wèn)題分解， O(n) S1=xS | xm 4) CPair1(S1, d

48、1) ; /*子問(wèn)題求解, 2T(n/2) CPair1(S2, d2);5) p=max(S1) ; /*用線性時(shí)間選擇算法,O(n/2) q=min(S2); /*用線性時(shí)間選擇算法,O(n/2) d=mind1, d2, q-p /* 合并，得到原問(wèn)題解, O(1)復(fù)雜度分析復(fù)雜度分析T(n)=O(nlogn)(1)2( )2 ( / 2)( )( / 2)(1)2(1)22 ( / 2)( )(1)2OnT nT nO nO nOnOnT nO nOnu二維的情形。pq選取一垂直線l:x=m來(lái)作為分割直線。 其中m為S中在x坐標(biāo)上第n/2 小、第(n/2 +1)小的2個(gè)點(diǎn)的x坐標(biāo)的平均

49、值。由此將平面S分割為子平面S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=mind1,d2，根據(jù)，根據(jù)d構(gòu)造點(diǎn)集構(gòu)造點(diǎn)集P1、P2S中的最接近點(diǎn)對(duì)(p,q)有3種情況1) 位于左邊的S1中，距離d2)位于右邊的S2中，距離d3)某個(gè)p, q，p左邊點(diǎn)集合P1 且q右邊點(diǎn)集合P2能否在線性時(shí)間能否在線性時(shí)間內(nèi)找到第三種情內(nèi)找到第三種情況下的況下的p,q？搜索區(qū)域：P1+P2u考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有distance(p，q)d。 滿(mǎn)足這個(gè)條件的滿(mǎn)足這個(gè)條件的P2中的點(diǎn)一定落在一個(gè)中的點(diǎn)一定落在一個(gè)對(duì)稱(chēng)于過(guò)對(duì)稱(chēng)于過(guò)p點(diǎn)的水平點(diǎn)的水平

50、線的線的d2d的矩形的矩形R中！中！u由d的意義可知，P2中不存在最近點(diǎn)對(duì)，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此可以推出矩形矩形R中最多只有中最多只有6個(gè)個(gè)S中中的點(diǎn)的點(diǎn)2個(gè)正方形的個(gè)正方形的6個(gè)頂點(diǎn)？對(duì)嗎？！個(gè)頂點(diǎn)？對(duì)嗎？！。u因此，在分治法的合并步驟中最多只需要檢查最多只需要檢查6n/2=3n個(gè)個(gè)候選者：候選者： n/2為左半邊要考慮的點(diǎn)數(shù)，為左半邊要考慮的點(diǎn)數(shù)，6為右半邊考慮的點(diǎn)數(shù)為右半邊考慮的點(diǎn)數(shù)證明證明:將矩形R的長(zhǎng)為2d的邊3等分，將它的長(zhǎng)為d的邊2等分，由此導(dǎo)出6個(gè)(d/2)(2d/3)的矩形。若矩形R中有多于6個(gè)S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè)(d/2)(2d/3)

51、的小矩形中有2個(gè)以上S中的點(diǎn)。設(shè)u，v是位于同一小矩形中的2個(gè)點(diǎn)，則distance(u,v)d。這與d的意義相矛盾。222223625)3/2()2/()()()()(dddvyuyvxux為了確切地知道要檢查哪6個(gè)點(diǎn)，可以將點(diǎn)p和區(qū)域P2中所有S2的點(diǎn)投影到垂直線l上。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對(duì)候選者的S2中點(diǎn)一定在矩形R中，所以它們?cè)谥本€l上的投影點(diǎn)距p在l上投影點(diǎn)的距離小于d。由上面的分析可知，這種投影點(diǎn)最多只有6個(gè)。因此，若將P1和P2中所有S中點(diǎn)按其y坐標(biāo)排好序，則對(duì)P1中所有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。 對(duì)P1中每一點(diǎn)最多只要檢查P2中排好

52、序的相繼6個(gè)點(diǎn)。double cpair2(S) n=|S|; if (n 2) return ;1、m=S中x坐標(biāo)第n/2 小、第(n/2 +1)小的2個(gè)點(diǎn)的x坐標(biāo)的平均值 構(gòu)造S1和S2； /S1=pS|x(p)m2、d1=cpair2(S1); d2=cpair2(S2);3、dm=min(d1,d2);4、設(shè)P1是S1中距垂直分割線l的距離在dm之內(nèi)的所有點(diǎn)組成的集合； P2是S2中距分割線l的距離在dm之內(nèi)所有點(diǎn)組成的集合； 將P1和P2中點(diǎn)依其y坐標(biāo)值排序； 并設(shè)X和Y是相應(yīng)的已排好序的點(diǎn)列；5、依次掃描X中各點(diǎn)，對(duì)于X中每個(gè)點(diǎn)，檢查Y中與其距離在dm之內(nèi)的所有點(diǎn)(最多最多6個(gè)個(gè))

53、，可以完成合并； 當(dāng)X中的掃描指針逐次向上移動(dòng)時(shí)，Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)移動(dòng)； 設(shè)dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離；6、d=min(dm,dl); return d;建議：修改算法，返回最近距離+最近點(diǎn)對(duì)復(fù)雜度分析復(fù)雜度分析T(n)=O(nlogn)44)()2/(2) 1 ()(nnnOnTOnT設(shè)計(jì)一個(gè)滿(mǎn)足以下要求的比賽日程表： 對(duì)n個(gè)選手，(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。日程表設(shè)計(jì)：1）n行、n列的表，2）對(duì)j=1，1in,tableij= tablei1代表第i個(gè)選手3）對(duì)1jn，1i n

54、,tableij為第i個(gè)選手在第j天遇到的對(duì)手按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了：1）左上角塊中的數(shù)字抄到右下角塊對(duì)應(yīng)位置2）左下角塊中的數(shù)字抄到右上角塊對(duì)應(yīng)位置1234567821436587341278564321876556781234658721437856341287654321天: 1 2 3 4 5 6 7選手n原理 將n=2k個(gè)選手的比賽分成依次求解21、22、2k個(gè)選手的比賽 n=2k個(gè)選手的比賽日

55、程在n/2=2k-1個(gè)選手的比賽日程基礎(chǔ)上，通過(guò)迭代得到 按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。 遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了：1）左上角塊中的數(shù)字抄到右下角塊對(duì)應(yīng)位置2）左下角塊中的數(shù)字抄到右上角塊對(duì)應(yīng)位置1221(1) 2k (k=1)個(gè)選手的比賽1234214334124321(2) 2k (k=2)個(gè)選手的比賽1234567821436587341278564321876556781234658721437856341287654321(3

56、) 2k (k=3)個(gè)選手的比賽n時(shí)間復(fù)雜性 O(4k)=O(2k)2)=O(n2)減治法減治法 vs 分治法 n對(duì)1個(gè)大問(wèn)題，分解為m個(gè)(e.g. m=2)子問(wèn)題后1）分治法： 求解多個(gè)子問(wèn)題，由多個(gè)子問(wèn)題解合并得到原問(wèn)題解 e.g. 歸并排序2）減治法：只需解決其中1個(gè)子問(wèn)題，就可得到原問(wèn)題解 e.g. 二分搜索，線性時(shí)間選擇n減治法的復(fù)雜性一般為 O(logmn)，O(n) 關(guān)于算法功能、性能一些思考n算法適應(yīng)性適應(yīng)性、與、與實(shí)際問(wèn)題契合程度實(shí)際問(wèn)題契合程度 每個(gè)算法面向特定問(wèn)題，有其特定適應(yīng)環(huán)境并非萬(wàn)能的； 應(yīng)用算法解實(shí)際問(wèn)題時(shí)，判斷算法適用性； 針對(duì)具體問(wèn)題，選擇、完善、設(shè)計(jì)/發(fā)明合

57、適的算法，保證算法結(jié)果能滿(mǎn)足實(shí)際需要；nE.g. 利用圖論中最短路徑算法，求解兩地之間的最短旅行線路優(yōu)先選擇某些區(qū)域內(nèi)線路考慮道路擁堵信息同時(shí)求出備選線路 關(guān)于算法功能、性能一些思考n面向?qū)嶋H應(yīng)用，判斷算法結(jié)果合理性，完善、修正算法 nE.g. 廣州地區(qū)基于基站密度的空間聚類(lèi) 地理上相近、類(lèi)型/性質(zhì)相同的點(diǎn)歸為同一類(lèi) 點(diǎn)：GSM基站，近1萬(wàn)個(gè) 類(lèi)型/性質(zhì)：基站與鄰基站間平均距離 關(guān)于算法功能、性能一些思考n面向?qū)嶋H應(yīng)用，判斷算法結(jié)果合理性，完善、修正算法 nE.g. 廣州地區(qū)基于基站密度的空間聚類(lèi) 地理上相近、類(lèi)型/性質(zhì)相同的點(diǎn)歸為同一類(lèi) 點(diǎn)：GSM基站，近1萬(wàn)個(gè) 類(lèi)型/性質(zhì)：基站與鄰基站間平

58、均距離 n問(wèn)題：區(qū)域內(nèi)存在“飛地”，不合理，導(dǎo)致區(qū)域形狀“毛刺”過(guò)多關(guān)于算法功能、性能一些思考n性能上，算法應(yīng)在用戶(hù)可接受的時(shí)間內(nèi)，采用合理計(jì)算資源，得到正確結(jié)果n兩方面入手： 1. 分析算法復(fù)雜性，看問(wèn)題本身是否具有極高復(fù)雜性 e.g. 漢諾塔問(wèn)題， 采用微機(jī)計(jì)算，5848億年； 如果采用并行計(jì)算實(shí)際上不可能： 1）北郵曙光集群，5000 億次/秒，2.2年 2） 天河二號(hào)天河二號(hào)， 5.49億 億次/秒， 12分鐘； 漢諾漢諾(Hanoi)塔塔印度教有一個(gè)古老的傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到

59、上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。 僧侶們預(yù)言：當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。廟宇和眾生也都將同歸于盡。Recursive solution hanoi(#disk, source, buffer, target):hanoi(n, left, middle,right);=/*將位于左柱的n片，借助中 柱，移植右柱hanoi(n-1, left, right, middle);/* 將

60、最高的n-1片，借助右 柱，移至中柱move(1, left, _, right); /*最底層的第n片，直接移至右柱hanoi(n-1, middle, left, right);/*右柱的n-1片，借助左柱， 移至右柱n-1關(guān)于算法功能、性能一些思考n兩方面入手(續(xù))： 2. 優(yōu)化算法性能 盡量在內(nèi)存中運(yùn)算，采用有效數(shù)據(jù)結(jié)構(gòu)，如數(shù)組；建立索引，加快數(shù)據(jù)訪問(wèn)nE.g. 基于空間聚類(lèi)的地理場(chǎng)景自動(dòng)識(shí)別 1. 4.2km4km區(qū)域，算法運(yùn)行時(shí)間 50分鐘 25分鐘 2. 全網(wǎng) 10,000平方公里運(yùn)行時(shí)間： 10,000/(4.24) * 25分鐘 248小時(shí)10天原始建筑物圖層（成都，覆蓋范圍約4.2km4km）(b)劃分后的高層(紅色)、中層（紫色）、低層（綠色