分治演算法 各個擊破獲得最後勝利 國立中央大學 資工系 江振瑞 教授

1. 分治演算法基本概念

分治解題策略 分治(divide and conquer)演算法使用分治解題策略解決問題。分治是很好的解題策略，可以很有效率的解決問題，又稱為分割再征服策略或各個擊破策略。一般而言，分治演算法具有三個階段: 分割階段:如果問題規模很小，就直接解決此問題；否則，將原本的問題分割(divide)成2個或多個子問題(subproblem)。 克服階段:用相同的演算法遞迴地(recirsively)解決或克服(conquer)所有的子問題。 合併階段:合併(merge)所有子問題的解答成為原本問題的解答。

使用分治解題策略的演算法 合併排序演算法 快速排序演算法 缺陷棋盤填滿演算法 二維求秩演算法 二維極大點演算法 最近二維點對演算法

2. 合併排序演算法

合併排序演算法 在本單元中，我們介紹使用分治解題策略的合併排序(merge sort) 演算法。 合併排序演算法由現代電腦之父，內儲程式(stored program)電腦架構發明之人之一的紐曼博士， 在西元1945 年發明。 約翰·馮·紐曼（John von Neumann，1903年12月28日－1957年2月8日），出生於匈牙利的美國籍猶太人數學家，現代電腦創始人之一。他在電腦科學、經濟、物理學中的量子力學及幾乎所有數學領域都作過重大貢獻。(圖及說明摘自維基百科)

合併排序演算法(續) 假設我們要使用合併排序演算法來將陣列A 中的n 個元素或資料(索引為0,...,n−1) 依照其值以由小而大的次序排列 克服: 遞迴地排序兩個子陣列。 合併: 最後合併兩個已完成排序的子陣列，即可完成原來陣列的排序。 合併排序演算法如Algorithm 6 (MergeSort)所示，而在此演算法中另外使用到如Algorithm 7所示的Merge演算法以合併二個子陣列。

合併排序演算法(續) (pr) If p=r then return A ► A只有一個元素

合併排序演算法(續) 1

合併排序演算法(續) 我們以下頁圖中的實例來看合併排序演算法的運作過程： 假設有一個陣列具有8 個元素85、24、63、50、17、31、96、50’，索引(index) 為0,...,7，其中50 與50’二個元素的值都是50，但是為了區別起見，我們將之標示為50 與50’。

合併排序演算法(續) 50 63

合併排序演算法(續) 在整個合併排序演算法的執行過程中，50 與50’的相對位置一直保持不變，因此如同氣泡排序與插入排序演算法一樣，合併排序演算法也是一個穩定(stable) 排序演算法。 合併排序演算法需要額外的與原來陣列大小相同的記憶體空間來輔助排序的進行，因此合併排序演算法不是就地(in place) 演算法，它的空間複雜度為O(n)，n 為需要排序陣列的元素個數。

合併排序演算法(續) T(n)=2T(n/2)+n 以下我們分析合併排序演算法的時間複雜度。

合併排序演算法(續) 我們遞迴地將T(n)=2T(n/2)+n中的n取代為n/2, n/4, ...，則我們可以得到: T(n) = 2T(n/2) + n = 2(2T(n/4)+(n/2)) + n = 4T(n/4) + n + n = 4(2T(n/8)+(n/4)) + 2n= 8T(n/8) + 3n = .... = 2k T(n/2k) + kn 當陣列只有一個元素時，合併排序演算法不會再進行遞迴呼叫，會直接回轉(return)，因此我們可得T(1) = 1。

合併排序演算法(續) 假設n = 2k，則k = log2 n。請注意，未來若我們不特別指定log函數的基底，則代表基底為2。 T(n) = n log n + 2k = n log n + n = O(n log n) 對所有的狀況(最佳、最差與平均狀況) 而言，合併排序演算法的時間複雜度都是O(n log n)。

3. 快速排序演算法

快速排序演算法 以下我們首先介紹快速排序(quick sort)演算法。此演算法由獲得計算機領域最高榮譽圖靈獎(Turing Award)的Hoare博士於1962年發表。 如其名稱所示，此排序演算法的排序速度相當快，因此使用相當廣泛。 查爾斯·安東尼·理察·霍爾爵士(Charles Antony Richard Hoare，縮寫為 C. A. R. Hoare，1934年1月11日－ )，生於斯里蘭卡可倫坡，英國計算機科學家，圖靈獎得主。他設計了可快速進行排序程序的快速排序(quick sort)演算法，提出可驗證程式正確性的霍爾邏輯(Hoare logic) 、以及提出可訂定並時程序(concurrent process)的交互作用(如哲學家用餐問題(dining philosophers problem)的交談循序程續(CSP, Communicating Sequential Processes)架構 。 (圖及說明摘自維基百科)

快速排序演算法(續) 快速排序演算法使用分治解題策略，其做法如下所述: 分割: 選一個元素p當作中樞(pivot)元素將陣列分割為2部份：SP及LP，其中SP (smaller part)包含所有小於或等於p的元素；而LP(larger part)則包含所有大於p的元素。 克服:完成陣列分割(partition)之後，快速排序演算法持續遞迴地(recursively)進行SP部份與LP部份的元素排序。 合併: 最後再將SP、p及LP合併即可完成排序。

快速排序演算法(續) Algorithm 8為快速排序演算法，此演算法使用二個指標(「左指標」l 與「右指標」r) 將陣列中索引在「左界」lb 及「右界」rb 範圍內的元素分割為二部份。

快速排序演算法(續) 大於或等於 p 的元素 小於 p 的元素或 r 等於(到達) lb

快速排序演算法(續) 以下我們舉實例來看快速排序演算法的運作過程。 假設有一個陣列具有8個元素85、24、63、50、17、50'、96、58 ，索引(index)為0,...,7，其中50與50’二個元素的值都是50，但是為了區別起見，我們將之標示為50與50’。 下圖展示快速排序演算法第一次將陣列分割為二個部份的過程。

快速排序演算法(續)

快速排序演算法(續) 在整個快速排序演算法的執行過程中，50與50’的相對位置產生變化，因此快速排序演算法不是一個穩定(stable)排序演算法。 快速排序演算法不需要額外的記憶體空間來輔助排序的進行，因此快速排序演算法是就地(in place)演算法，它的空間複雜度為O(1)。

快速排序演算法(續) 以下我們分析快速排序演算法的時間複雜度。 在最佳狀況下，快速排序演算法每次都將陣列分割為二個大小相同或幾乎相同的子陣列(我們可以將分割後的二個子陣列都視為是原陣列的1/2大小) 。 假設利用快速排序演算法針對具有n 個元素的陣列(也就是說輸入規模為n) 進行排序的時間複雜度為T(n)，針對最佳狀況，我們可以得到以下的式子: T(n)=n+2T(n/2) 這是因為當指標l 持續往右移，而同時指標r 持續往左移而交叉時(也就是說 l  r 時)，代表陣列分割完成。指標每次移動一個位置需要一次的數值比較操作，因此要完成陣列分割需要執行n 次數值比較操作。而陣列分割完成之後，快速排序演算法就利用遞迴的方式分別完成二個大小相同的(均為n/2) 子陣列排序。 如合併排序演算法的分析一樣，我們可得 T(n)=O(n log n)

快速排序演算法(續) 以下我們分析快速排序演算法的最差狀況時間複雜度。 當陣列的n 個元素已經依由小而大的方式排列的情況下會產生最差狀況。 在此情況下，快速排序演算法首先在經過n 次數值比較操作之後，將陣列分割為單一一個所有元素都比中樞元素小，具有n − 1 個元素的子陣列。 經過遞迴呼叫，快速排序演算法再利用n − 1 次數值比較操作將陣列分割為單一一個所有元素都比新中樞元素小，具有n − 2 個元素的子陣列。 如此不斷遞迴執行，直到陣列分割出僅包含一個元素的子陣列為止。 同樣假設快速排序演算法的時間複雜度為T(n)，針對最差狀況，我們可以得到以下的式子: T(n) = n + (n − 1) + (n − 2) + ... + 2 = (n+2)(n − 1)/2 = O(n2)

快速排序演算法(續)

快速排序演算法(續)

快速排序演算法(續) n-1, n-2,…,1

快速排序演算法(續)

排序演算法比較

4. 缺陷棋盤填滿演算法

缺陷棋盤填滿演算法說明 缺陷棋盤填滿演算法使用分治策略解決缺陷棋盤填滿問題，使用三格骨牌填滿缺陷棋盤 以下我們先定義甚麼是棋盤、缺陷棋盤及三格骨牌 然後我們定義缺陷棋盤填滿問題 最後我們介紹缺陷棋盤填滿演算法

棋盤的定義 一個棋盤是一個 n x n方格(grid)，具有n2個單格(cell)，其中n2而且n是2的幂(a power a 2)

缺陷棋盤的定義 缺陷棋盤是有一單格(cell)無法使用的棋盤。 X 8x8 X 4x4 X 2x2

三格骨牌的定義 三格骨牌(Triomino)為一L型骨牌，可填滿一棋盤上的3個單格。 三格骨牌有4種方向。

缺陷棋盤填滿問題 放置(n2 - 1)/3 個三格骨牌在n x n缺陷棋盤上，使得全部(n2 – 1)個非缺陷單格都被填滿。 X 8x8 For the tiling to be possible, (n2 - 1) must be divisible by 3 whenever n is a power of 2. So, the tiling algorithm that follows actually provides a proof the this is so. 4x4 X X 2x2

缺陷棋盤填滿演算法 Algorithm 缺陷棋盤填滿演算法 Input: n x n缺陷棋盤， n2而且n是2的幂 Output: 以三格骨牌填滿的n x n缺陷棋盤 步驟1: 若n=2，則旋轉一個三格骨牌直接填滿缺陷棋盤，回傳此2 x 2缺陷棋盤並結束。 步驟2: 將缺陷棋盤分為3個(n/2) x (n/2)棋盤及1個(n/2) x (n/2)缺陷棋盤，旋轉一個三格骨牌填滿3個棋盤中相鄰的單格，可使3個棋盤成為缺陷棋盤，我們可得4個(n/2) x (n/2)缺陷棋盤。 步驟3: 遞迴地使用缺陷棋盤填滿演算法以三格骨牌填滿步驟2的4個(n/2) x (n/2)缺陷棋盤，回傳原始n x n缺陷棋盤並結束。

缺陷棋盤填滿演算法實例 將8 x 8缺陷棋盤分割成4個更小的 4 x 4 棋盤。

缺陷棋盤填滿演算法實例(續) 放置1個三格骨牌在3個4 x 4正常棋盤的相鄰單格，讓他們也變成缺陷棋盤。

缺陷棋盤填滿演算法實例(續) 以遞迴方式填滿右上角之缺陷4 x 4棋盤。 X 以遞迴方式填滿左上角之缺陷4 x 4棋盤….。

5. 二維求秩演算法

二維求秩演算法說明 二維求秩(2D rank finding)演算法使用分治策略解決二維求秩問題 以下我們先定義支配(dominate)及 秩(rank) 然後我們定義二維求秩問題 最後我們介紹二維求秩演算法

支配及秩的定義 令A = (ax, ay), B = (bx, by)為二維XY平面上的點，則我們說A支配(dominate)B(記為AB)若且唯若 ax> bx 且 ay > by。 給定一個由二維平面點所構成的集合S，點A之秩(rank)定義為集合S中有多少個點被A所支配。 E.G.: BA, CA, DC, EA E.G.: rank(A)=0, rank(B)=1, rank(C)=1, rank(D)=2, rank(E)=2

二維求秩問題 給定一個由n個二維平面點所構成的集合S，求出S中所有點的秩。 可以用窮舉(exhaustive)演算法，比較所有的可能成對點，時間複雜度為O(n2)。

二維求秩演算法 Algorithm 二維求秩演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有點的秩(rank) 步驟1: 若n=1，則回傳S中唯一一個點的秩為0並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維求秩演算法分別求出SL與SR中所有點的秩。 步驟4: 根據Y軸值排序所有在S(S=SLSR)中的點，依序由小而大掃描所有點，求出每一個在SR的點i排在多少在SL的點的後面(記為updatei)，並將點i的秩加上updatei，最後回傳S中所有點的秩。

二維求秩演算法範例 假定給定平面上10個點，依其X軸中位數(median)畫出直線L將之分為二個集合SL與SR。下圖顯示SR中所有點的秩的更新。

二維求秩演算法時間複雜度分析 步驟時間複雜度: 步驟2: c1n log n (排序) 步驟4: c2n log n (排序) Algorithm 二維求秩演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有點的秩(rank) 步驟1: 若n=1，則回傳S中唯一一個點的秩為0並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維求秩演算法分別求出SL與SR中所有點的秩。 步驟4: 根據Y軸值排序所有在S(S=SLSR)中的點，依序掃描所有點且求出每一個在SR的點i排在多少在SL的點的後面(記為updatei)，並將點i的秩加上updatei；最後回傳S中所有點的秩並結束。 步驟時間複雜度: 步驟2: c1n log n (排序) 步驟4: c2n log n (排序) 總時間複雜度: T(n) = 2T(n/2) + c1n log n + c2n log n = 2T(n/2) + cn log n = 2(2T(n/4)+c(n/2) log (n/2))+ cn log n = 4T(n/4) + cn log (n/2) + cn log n = nT(1) + cn(log n + log (n/2)+ log (n/4) +…+ log 2)  nT(1) + cn (log n (log n+ log 2))/2 (其中T(1)=1) = O(n log2n)

6. 二維極大點演算法

二維極大點演算法說明 二維極大點(2D maxima finding)演算法使用分治策略解決二維極大點問題 以下我們先定義支配(dominate)及 極大點(maxima) 然後我們定義二維極大點問題 最後我們介紹二維極大點演算法

支配及極大點的定義 令A = (ax, ay), B = (bx, by)為二維XY平面上的點，則我們說A支配(dominate)B(記為AB)若且唯若 ax> bx 且 ax > by。 如果一個點不被任何其他點所支配，我們就稱此點不被支配(non-dominated)，或稱此點為極大點(maxima)。 極大點不只一個。

二維極大點問題 給定一個由n個二維平面點所構成的集合S，求出S中的極大點(maxima)。 可以用窮舉(exhaustive)演算法，比較所有的可能成對點，其時間複雜度為O(n2)。

二維極大點演算法 Algorithm 二維極大點演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有的極大點(maxima) 步驟1: 若n=1，則回傳S中唯一一個點為極大點並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維極大點演算法分別求出SL與SR中所有的極大點。 步驟4: 在SR的極大點中找出最大的Y軸值y*。 對每個在SL中的極大點，如果該點的Y軸值小於y*，則標示該點為不是極大點。回傳SR中的極大點和SL中未被標示的極大點。

二維極大點演算法範例 假定給定平面上10個點，依其X軸中位數(median)畫出直線L將之分為二個集合SL與SR。下圖顯示SL中極大點的更新。

二維極大點演算法時間複雜度分析 步驟時間複雜度: 步驟2: c1n log n (以排序算法求出中位數) 步驟4: c2n (依序檢查) Algorithm 二維極大點演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有的極大點(maxima) 步驟1: 若n=1，則回傳S中唯一一個點為極大點並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維極大點演算法分別求出SL與SR中所有的極大點。 步驟4: 在SR的極大點中找出最大的Y軸值y*。 對每個在SL中的極大點，如果該點的Y軸值小於y*，則標示該點為不是極大點。回傳SR中的極大點和SL中未被標示的極大點。 步驟時間複雜度: 步驟2: c1n log n (以排序算法求出中位數) 步驟4: c2n (依序檢查) 總時間複雜度: T(n) = 2T(n/2) + c1n log n + c2n = 2T(n/2) + cn log n = 2(2T(n/4)+c(n/2) log (n/2))+ cn log n = 4T(n/4) + cn log (n/2) + cn log n = nT(1) + cn(log n + log (n/2)+ log (n/4) +…+ log 2) = nT(1) + cn (log n (log n+ log 2))/2 (其中T(1)=1) = O(n log2n)

二維極大點演算法時間複雜度分析(續) 步驟時間複雜度: 步驟2: c1n (以刪尋演算法求中位數) 步驟4: c2n (依序檢查) Algorithm 二維極大點演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有的極大點(maxima) 步驟1: 若n=1，則回傳S中唯一一個點為極大點並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維極大點演算法分別求出SL與SR中所有的極大點。 步驟4: 在SR的極大點中找出最大的Y軸值y*。 對每個在SL中的極大點，如果該點的Y軸值小於y*，則標示該點為不是極大點。回傳SR中的極大點和SL中未被標示的極大點。 步驟時間複雜度: 步驟2: c1n (以刪尋演算法求中位數) 步驟4: c2n (依序檢查) 總時間複雜度: T(n) = 2T(n/2) + c1n + c2n = 2T(n/2) + cn = 2(2T(n/4)+c(n/2))+ cn = 4T(n/4) + cn + cn = nT(1) + cn+cn+…+cn (其中總共log n個cn) = nT(1) + cn log n (其中T(1)=1) = O(n log n)

7. 最近二維點對演算法

最近二維點對演算法說明 最近二維點對(closest pair of 2D points) 演算法使用分治策略解決最近二維點對問題 以下我們先定義最近二維點對問題 然後我們介紹最近二維點對演算法

最近二維點對問題 給定n個二維平面點，找出其中距離最近的二個點的距離。 可以用窮舉(exhaustive)演算法，比較所有的成對點，其時間複雜度為O(n2)。

最近二維點對演算法 Algorithm 最近二維點對演算法 Input: n個二維平面點所構成的集合S，n2 Output: 集合S中距離最近的二個點的距離d 步驟1: 根據X軸值與Y軸值來事先排序S中的點。 步驟2: 若n=2，則回傳S中二點的距離d並結束。 步驟3: 找出所有點的X軸中位數(median)m畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟4: 遞迴地使用二維點對演算法分別求出SL與SR中最近二維點對的距離dL與dR，且令 d = min(dL, dR)。

最近二維點對演算法(續) 步驟5: 將X軸值介於m-d與m+d的所有點的Y軸值投射至直線L上。針對於每個X軸值落在範圍介於m-d與m之間的點p，以yp記錄其Y軸值，並尋找所有X軸值落在範圍介於m與m+d之間，且Y軸值介於yP+d 與 yP-d之間的所有點，若存在一點與p之距離為小於d的d’，則令d=d’。回傳d並結束執行。

最近二維點對演算法執行說明

最近二維點對演算法時間複雜度分析 步驟時間複雜度: 步驟 1: c1n log n (事先排序) 步驟 2~5: Algorithm 最近二維點對演算法 Input: n個二維平面點所構成的集合S，n2 Output: 集合S中距離最近的二個點的距離d 步驟1: 根據X軸值與Y軸值來事先排序S中的點。 步驟2: 若n=2，則回傳S中二點的距離d並結束。 步驟3: 找出所有點的X軸中位數(median)m畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟4: 遞迴地使用二維點對演算法分別求出SL與SR中最近二維點對的距離dL與dR，且令 d = min(dL, dR)。 步驟5: 將X軸值介於m-d與m+d的所有點的Y軸值投射至直線L上。針對於每個X軸值落在範圍介於m-d與m之間的點p，以yp記錄其Y軸值，並尋找所有X軸值落在範圍介於m與m+d之間，且Y軸值介於yP+d 與 yP-d之間的所有點，若存在一點與p之距離為小於d的d’，則令d=d’。回傳d並結束執行。 步驟時間複雜度: 步驟 1: c1n log n (事先排序) 步驟 2~5: T’(n) = c2n log n 總時間複雜度: T(n) = c1n log n + c2n log n = O(n log n)

8. 最大連續子序列和問題

最大連續子序列和(Maximum Contiguous Subsequence Sum, MCSS)問題 給定一個包含n個正或負整數的序列S=s1, s2,…, sn，找出S的連續子序列，使得子序列中的元素總和最大。 範例1: 令 S=-2,1,-3,4,-1,2,1,-5,4, 則最大連續子序列和為4+(-1)+2+1 = 6。 範例2: 令 S=-2,-6,-3,-4,-10,-5,-1,-7, 則最大連續子序列和為-1。

窮舉演算法1 (Exhaustive Algorithm 1) Input: 序列S=s1, s2,…, sn Output: 最大連續子序列sl,…,sr及其和m m - for i1 to n do for j i to n do t0 for ki to j do tt+sk if t>m then mt;li;rj return l, r, m Time Complexity: O(n3)

窮舉演算法2 (Exhaustive Algorithm 2) Input: 序列S=s1, s2,…, sn Output:最大連續子序列sl,…,sr及其和m m - for i1 to n do t0 for j i to n do tt+sj if t>m then m=t;li;rj return l, r, m Time Complexity: O(n2)

分治演算法 Time Complexity: O(n log n) Algorithm MS(S, l, r) //最大子序列和分治演算法 Input: 序列S=s1, s2,…, sn Output:最大連續子序列和m if (l=r) then return sl md(r-l)/2 //md: middle mlMS(S, l , md) //ml: max for left mrMS(S, md+1, r) //mr: max for right mbl -; t0 //mbl: max for boundary left for imd downto l do tt+si if (t>mbl) then mblt mbr -; t0 //mbr: max for boundary right for i md+1 to r do if (t>mbr) then mbrt if (mbl>0 and mbr>0) then mbmbl+mbr else mbMax(mbr, mbl) return Max(ml, mr, mb)

Q&A