算法設(shè)計(jì)技巧與分析 分治法(第6章)

2024/3/210第六章分治法分治法的基本模式6.1

引言6.2

二分搜索6.3

歸并排序6.4

分治法的基本模式應(yīng)用6.5

選擇:找第k小元素6.6

快速排序6.7

大整數(shù)的乘法6.8

矩陣乘法6.9

最近點(diǎn)對(duì)問(wèn)題2024/3/2116.1引言問(wèn)題在序列A[1..n]中找最小和最大元素。思想在序列A[1……n]中找最小和最大元素x,y[if(n<=2)直接比較得結(jié)果;else

在序列A[1……mid]中找最小和最大元素x1,y1;

在序列A[mid+1…..n]中找最小和最大元素x2,y2;x=min{x1,x2};y=max{y1,y2};]2024/3/2126.1引言Algorithm6.1MINMAX2024/3/2136.1引言2024/3/2146.1引言2024/3/2156.2二分檢索問(wèn)題在序列A[1..n]中查找x，若找到返回下標(biāo)，否則返回0。思想在序列A[1……n]中找x[if序列長(zhǎng)度n為0，返回0;elsecasex=A[mid]:返回mid;casex<A[mid]:在序列A[1……mid-1]中找x;casex>A[mid]:在序列A[mid+1…..n]中找x;]Algorithm6.2BINARYSEARCHERC最壞情況時(shí)間復(fù)雜度：

(logn)2024/3/2166.2二分檢索算法分析

設(shè)C(n)表示算法對(duì)大小為n的數(shù)組在最壞情況下所指向的比較次數(shù)。則有如下遞推式2024/3/2176.2二分檢索

由于2024/3/2186.3歸并排序問(wèn)題將序列A[1..n]中元素按照升序排序。思想將序列A[1……n]中元素排序[if序列長(zhǎng)度n>1

將序列A[1……mid]中元素排序;

將序列A[mid+1…..n]中元素排序;

歸并兩個(gè)有序序列A[1……mid]和A[mid+1…..n]；

]2024/3/2196.3歸并排序2024/3/21106.3歸并排序2024/3/21116.3歸并排序算法分析 首先，假定n是2的冪，即n=2k。令C(n)表示n個(gè)元素排序需要比較的次數(shù)，顯然n=1，有C(1)=0。當(dāng)n>1，執(zhí)行步驟3和4的比較次數(shù)都是C(n/2)。而步驟5的比較次數(shù)根據(jù)觀察結(jié)論1.1可知介于n/2和n-1之間。因此所需的最小比較次數(shù)由下式確定：2024/3/21126.3歸并排序

所需的最大比較次數(shù)則是：2024/3/21136.3歸并排序2024/3/21146.4分治法的基本模式關(guān)鍵步驟劃分：將輸入分成p≤n個(gè)部分處理子問(wèn)題：如果問(wèn)題的規(guī)模大于某個(gè)預(yù)定的閾值n0，則執(zhí)行p個(gè)遞歸調(diào)用。合并：組合p個(gè)遞歸調(diào)用的解來(lái)得到期望的輸出值。合并步驟對(duì)于執(zhí)行一個(gè)實(shí)際的分治算法是非常關(guān)鍵的，算法的效率很大程度上取決于如何明智地實(shí)現(xiàn)這一步。劃分的步驟在幾乎所有的分治算法中是不變的：把輸入數(shù)據(jù)分成p部分，并且轉(zhuǎn)到處理子問(wèn)題這一步。因此，它的時(shí)間為O(n)，甚至是O(1)。2024/3/2115分而治之法算法的模式若問(wèn)題實(shí)例I大小“較小”，則直接求解并返回結(jié)果；否則進(jìn)行下一步；（divide）將I分成m個(gè)大小基本相同的子實(shí)例I1,I2,…,Im；（conquer）對(duì)于每個(gè)子實(shí)例遞歸地求解得到它們的解；（combine）將子實(shí)例的解合并得到實(shí)例I的解6.4分治法的基本模式2024/3/2116實(shí)例I

:

？

分解實(shí)例I

1:

？實(shí)例I2:

？……實(shí)例I

m:

？

分解……

遞歸求解實(shí)例I

1:

y1實(shí)例I

2:

y2……實(shí)例I

m:

ym

合并實(shí)例I

:

y分治法的直觀描述2024/3/21176.5選擇:找中值和第k小元素選擇問(wèn)題

找出序列A[1..n]中的第k小元素。特別地，當(dāng)k=

n/2

時(shí)，即找中值元素。算法1：排序時(shí)間復(fù)雜度:

(nlogn)

尋找中項(xiàng)最直接的方法是對(duì)所有元素排序并取出中間的一個(gè)元素。這個(gè)算法需要(nlogn)時(shí)間。2024/3/21186.5選擇:找中值和第k小元素算法2：一個(gè)最壞時(shí)間復(fù)雜度為

(n2)的分治法思想

對(duì)于集合A[1..n]中的元素，用其中某元素v進(jìn)行劃分：

A1={a|a<v且aA}，

A2={a|a=v且aA}，

A3={a|a>v且aA}。

case|A1|

k：?jiǎn)栴}歸結(jié)為在A1中找第k小元素；

case|A1|+|A2|>=k：v就是第k小元素；

case|A1|+|A2|<k：?jiǎn)栴}歸結(jié)為在A3中找第k-|A1|-|A2|小元素。 對(duì)于第一、第三種情形，在A1或A3上重復(fù)上述過(guò)程直到找到所要找的元素為止。

2024/3/2119算法3：一個(gè)最壞時(shí)間復(fù)雜度為

(n)的分治法思想

在上述算法中，劃分元素為二次取中值得到，這樣就保證了子問(wèn)題A1或A3的大小變?yōu)锳大小的p倍（p為常數(shù)且0<p<1）。由此所得算法的最壞情況時(shí)間為

(n)。Algorithm6.4

SELECT6.5選擇:找中值和第k小元素2024/3/21206.5選擇:找中值和第k小元素2024/3/2121例：假設(shè)A={8，33，17，51，57，49，35，11，25，37，14，3，2，13，52，12，6，29，32，54，5，16，22，23，7，65},尋找中項(xiàng)k=[26/2]=13。閾值由44對(duì)于本題過(guò)大，假設(shè)改為6，首先將數(shù)集劃分為5組，

{8，33，17，51，57} {49，35，11，25，37} {14，3，2，13，52} {12，6，29，32，54} {5，16，22，23，7}{65}6.5選擇:找中值和第k小元素2024/3/2122對(duì)每組進(jìn)行排序

{8，17，33，51，57} {11，25，35，37，49} {2，3，13，14，52} {6，12，

29，32，54} {5，7，16，22，23}{65} M={33，35，13，29，16}

遞歸找到M中的中項(xiàng)：mm=296.5選擇:找中值和第k小元素2024/3/2123將A分為三個(gè)子序列：A1={8，17，11，25，14，3，2，13，12，6，5，16，22，23，7}A2={29}A3={22，51，57，49，35，37，52，32，54，65}因?yàn)閨A1|=15>k=13所以第13小的元素在A1中。令A(yù)=A1重復(fù)上述過(guò)程。6.5選擇:找中值和第k小元素2024/3/2124A={8，17，11，25，14，3，2，13，12，6，5，16，22，23，7}將數(shù)集分為3組

{8，17，11，25，14} {3，2，13，12，6} {5，16，22，23，7}M={14，6，16} mm=14 A1={8，11，3，2，13，12，6，5，7} A2={14} A3={17，25，16，22，23}6.5選擇:找中值和第k小元素2024/3/2125|A1|+|A2|=10<k=13，故第13小的元素在A3中。設(shè)A=A3，由于|A3|=5<設(shè)定的閾值6，故直接對(duì)A進(jìn)行排序找到第3小的元素（3=13-10）。最終算法返回A[3]=22，也即給定的序列的中項(xiàng)是22。6.5選擇:找中值和第k小元素2024/3/2126算法分析 如下圖所示，已將數(shù)集中的元素劃分為具有5元素的各個(gè)組，每個(gè)組從低到頂按升序排列。6.5選擇:找中值和第k小元素2024/3/2127

令A(yù)1’表示小于或等于mm的元素集，A3’表示大于或等于mm的元素集，根據(jù)算法的定義，A1是嚴(yán)格小于mm的元素集，A3是嚴(yán)格大于mm的元素集，故：6.5選擇:找中值和第k小元素2024/3/2128下面來(lái)分析算法的運(yùn)行時(shí)間T(n)(1)(n)(n)(n)(1)T(0.7n+1.2)2024/3/2129

對(duì)于步驟7，希望去掉常量1.2，令0.7n+1.2≤，則有0.7n+1.2≤0.75-1，即當(dāng)n≥44時(shí)，這個(gè)不等式成立。

故有下述遞推式：6.5選擇:找中值和第k小元素2024/3/21306.5選擇:找中值和第k小元素2024/3/21316.6快速排序思想

快速分類(lèi)算法是由著名的計(jì)算機(jī)科學(xué)家霍爾（C.A.R.Hoare）根據(jù)分治策略設(shè)計(jì)的一種高效率的分類(lèi)算法?；舅枷胧牵瑢?duì)于輸入的子序列A[p..q]，快速分類(lèi)分三步走：

(1)分解(Divide)：將A[p..q]劃分成兩個(gè)非空的子序列A[p..j]和A[j+1..q]，使得A[p..j]中的任一元素小于或等于A[j+1..q]中的任一元素。下標(biāo)j在劃分過(guò)程中確定.

(2)遞歸求解(Conquer)：通過(guò)遞歸調(diào)用快速分類(lèi)算法分別對(duì)A[p..j-1]和A[j+1..q]進(jìn)行分類(lèi)。

(3)合并(Merger)：由劃分的特點(diǎn)知，在A[p..j-1]和A[j+1..q]都分好類(lèi)后不需任何計(jì)算A[p..q]就已分好類(lèi)。2024/3/21326.6快速排序

QUICKSORT排序算法具有(nlogn)的平均運(yùn)行時(shí)間，這個(gè)算法優(yōu)于MERGESORT的一點(diǎn)是它在原位上排序，即對(duì)于被排序的元素，不需要輔助的存儲(chǔ)空間。

下面介紹劃分SPLIT算法，它是算法QUICKSORT算法的基礎(chǔ)。2024/3/21336.6快速排序2024/3/21346.6快速排序例：將算法應(yīng)用于數(shù)組{5，7，1，6，4，8，3，2}.2024/3/21356.6快速排序2024/3/21366.6快速排序快速排序算法思想

要排序的元素A[low…h(huán)igh]通過(guò)算法SPLIT重新排列元素，使得原先在A[low]中的主元占據(jù)其正確的位置A[w]，并且所有小于或等于A[w]的元素的位置處于A[low…w-1]，而所有大于A[w]的元素所處的位置是A[w+1…h(huán)igh]。子數(shù)組A[low…w-1]和A[w+1…h(huán)igh]遞歸地排序，產(chǎn)生整個(gè)排序數(shù)組。2024/3/21376.6快速排序2024/3/21386.6快速排序例：假設(shè)對(duì)數(shù)組{4，6，3，1， 8，7，2，5}排序。2024/3/21396.6快速排序快速排序算法時(shí)間復(fù)雜度分析最壞情況:

(n2)最好情況:

(nlogn)平均情況:

(nlogn)2024/3/21406.6快速排序最壞情況:

(n2)

最壞情況發(fā)生在輸入數(shù)組已經(jīng)是非降序排列的，而對(duì)于算法QUICKSORT的每次調(diào)用，都發(fā)生在主元A[low]是數(shù)組中最小的元素的情況，這意味著將得到w=low，因而僅存在一個(gè)有效的遞歸調(diào)用，而另一個(gè)調(diào)用成為對(duì)一個(gè)空數(shù)組的調(diào)用。

因此，如果算法從調(diào)用QUICKSORT(A,1,n)開(kāi)始，下一步的兩個(gè)遞歸調(diào)用分別是QUICKSORT(A,1,0)和QUICKSORT(A,2,n)，第一個(gè)是無(wú)效的調(diào)用。2024/3/21416.6快速排序

此時(shí)，對(duì)于quicksort的n次調(diào)用就為：

quicksort(A,1,n),quicksort(A,2,n),…,quicksort(A,n,n)

接著，調(diào)用SPLIT算法： SPLIT(A[1…n],w),SPLIT(A[2…n],w),…,SPLIT(A[n…n],w)

由于對(duì)于輸入為j的元素，SPLIT算法執(zhí)行的比較次數(shù)為j-1。故總的比較次數(shù)為

2024/3/21426.6快速排序2024/3/21436.6快速排序平均情況:

(nlogn)

有 可得2024/3/21446.6快速排序

將上式的n用n-1代替，可得 兩式相減，整理后 令 可得 解得2024/3/21456.6快速排序2024/3/2146回顧一個(gè)遞歸方程的解

2024/3/2147回顧一個(gè)遞歸方程的解

2024/3/21486.7大整數(shù)乘法問(wèn)題

設(shè)u和v分別兩個(gè)n-bit的整數(shù)（n是2的k次冪），求其乘積uv。算法1

——傳統(tǒng)算法：

(n2)算法2

——分治算法思想2024/3/21496.7大整數(shù)乘法2024/3/21506.7大整數(shù)乘法2024/3/21516.7大整數(shù)乘法2024/3/21526.7大整數(shù)乘法2024/3/21536.8矩陣乘法問(wèn)題設(shè)A和B是nn矩陣，求其乘積C=AB.算法1——傳統(tǒng)算法思想時(shí)間復(fù)雜度：

(n3)——n3次乘法和n3–n2次加法2024/3/21546.8矩陣乘法算法2——遞歸算法思想2024/3/21556.8矩陣乘法2024/3/21566.8矩陣乘法算法3——Strassen’salgorithm思想 算法的基本思想就是增加加減法的次數(shù)減少乘法的次數(shù)。這個(gè)算法最終用了7次n/2×n/2矩陣乘法和18次n/2×n/2矩陣加法。2024/3/21576.8矩陣乘法2024/3/21586.8矩陣乘法2024/3/21596.8矩陣乘法三個(gè)算法的比較2024/3/21606.9最近點(diǎn)對(duì)問(wèn)題

最近點(diǎn)對(duì)問(wèn)題

在應(yīng)用中，常用諸如點(diǎn)、圓等簡(jiǎn)單的幾何對(duì)象代表現(xiàn)實(shí)世界中的實(shí)體。在涉及這些幾何對(duì)象的問(wèn)題中，常需要了解其鄰域中其它幾何對(duì)象的信息。例如，在空中交通控制問(wèn)題中，若將飛機(jī)作為空中移動(dòng)的一個(gè)點(diǎn)來(lái)看待，則具有最大碰撞危險(xiǎn)的2架飛機(jī)就是空中最接近的一對(duì)點(diǎn)。這類(lèi)問(wèn)題是計(jì)算幾何學(xué)中研究的基本問(wèn)題之一。下面我們著重考慮平面上的最接近點(diǎn)對(duì)問(wèn)題。給定平面上n個(gè)點(diǎn)(xi,yi)，1≤i≤n，找出其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)的距離最短。2024/3/2161

算法思想算法一（直接法）：通過(guò)檢查所有的n(n-1)/2對(duì)點(diǎn)，并計(jì)算每一對(duì)點(diǎn)的距離，即可找出距離最近的一對(duì)點(diǎn)。這種方法所需的時(shí)間為O(n2)。算法二（分治法）：

1）當(dāng)n較小時(shí)，用直接法求最近點(diǎn)對(duì)；

2）當(dāng)n較大時(shí)，將點(diǎn)集分成大致相等的兩部分A和B，（遞歸地）確定A和B中的最近點(diǎn)對(duì)，確定一點(diǎn)在A中，另一點(diǎn)