分而治之法 5 2019/8/20 演算法 ＿ 第五章.

Presentation on theme: "分而治之法 5 2019/8/20 演算法 ＿ 第五章."— Presentation transcript:

1 分而治之法 5 2019/8/20 演算法 ＿ 第五章

2 什麼叫分而治之法 針對一個有 n 筆輸入的問題，它把輸入分解成 k（1 < k  n）個獨立的小集合 這導致原問題變成k個小問題
2019/8/20 演算法 ＿ 第五章

3 什麼叫分而治之法 分而治之法分因此可以分成三個主要步驟：
如果要處理的資料量已經夠少，那麼用直接的方式解決；否則，把輸入資料分解成兩個獨立的小集合 求出每一個小問題的解，並且 把這兩個小問題的解組合起來，成為原來的大問題的解 2019/8/20 演算法 ＿ 第五章

4 什麼叫分而治之法 一個分而治之演算法的時間複雜度 T(n) 可以用下列的遞迴關係來求得：
其中 S(n) 是將原問題分解成兩個小問題所需要花的時間，M(n) 是將兩個小問題的解組合成原問題的解所需要花的時間，b 跟 c 都是常數 2019/8/20 演算法 ＿ 第五章

5 合併排序法 2019/8/20 演算法 ＿ 第五章

6 合併排序法 2019/8/20 演算法 ＿ 第五章

7 合併排序法 22 5 79 1 63 13 56 17 43 20 Merge_Sort(1, 10) 22 5 79 1 63 Merge_Sort(1, 5) 22 5 79 Merge_Sort(1, 3) 22 5 Merge_Sort(1, 2) Merge_Sort(1, 1) ; return 22 2019/8/20 演算法 ＿ 第五章

8 合併排序法 22 5 79 1 63 13 56 17 43 20 22 Merge_Sort(low, mid) = Merge_Sort(1, 1) // low =1, mid = 1, high =2 Merge_Sort(mid+1, high) = Merge_Sort(2, 2); return 5 5 22 Merge(1, 1, 2) 2019/8/20 演算法 ＿ 第五章

9 合併排序法 22 5 79 1 63 13 56 17 43 20 22 Merge_Sort(low, mid) = Merge_Sort(1, 1) // low =1, mid = 1, high =2 5 Merge_Sort(mid+1, high) = Merge_Sort(2, 2) 5 22 Merge(1, 1, 2); return // low =1, mid =2, high =3 79 Merge_Sort(mid+1, high) = Merge_Sort(3, 3) Merge(1, 2, 3); return // low =1, mid =2, high =3 5 22 79 演算法 ＿ 第五章 2019/8/20

10 合併排序法 演算法 5.1 的 S(n) 是常數時間 O(1)，因為它的分割只需要計算 mid
演算法 5.1 的 M(n) 做的是合併的工作，所需要的計算時間跟 n 成正比 因此，演算法 5.1 的時間複雜度 T(n) 可以用下列的遞迴關係來描述： 2019/8/20 演算法 ＿ 第五章

11 合併排序法 如果 2k < n  2k+1，則 T(n)  T(2k+1)。因此T(n) = O(n log n)
2019/8/20 演算法 ＿ 第五章

12 合併排序法 我們在第二章證明了排序問題的最壞情況計算複雜度是 (n log n)
而合併排序法的最壞情況時間複雜度又是T(n) = O(n log n) 因此，合併排序法已經是在最壞情況下的最佳化演算法了 2019/8/20 演算法 ＿ 第五章

13 合併排序法 合併排序法的平均時間複雜度又是多少？ 作業 2.18 題證明了「排序問題的平均情況計算複雜度下限也是 (n log n)」
因此，合併排序法的平均情況時間複雜度必然大於等於 O(n log n) 2019/8/20 演算法 ＿ 第五章

14 合併排序法 但是，任何一個演算法的平均情況複雜度必然小於等於它的最壞情況複雜度，合併排序法也不例外
因此，合併排序法的平均情況複雜度必然小於等於 O(n log n) 綜合以上的討論，我們因此得到合併排序法的平均情況複雜度也等於O (n log n) 這也意味著合併排序法也是平均情況下的最佳化演算法 2019/8/20 演算法 ＿ 第五章

15 快速排序法 快速排序法的最壞情況時間複雜度高達O(n2) 但是平均起來它通常都跑得比合併排序法快 快速排序法也是使用分而治之法
2019/8/20 演算法 ＿ 第五章

16 快速排序法 先從待排序的資料中選擇一筆樞鈕資料 接下來，將待排序的記錄重新排列使得 最後，樞鈕左方的記錄以及樞鈕右方的記錄分別獨立地做排序
在樞鈕左方的資料都小於或等於樞鈕 在樞鈕右方的資料則都大於或等於樞鈕 最後，樞鈕左方的記錄以及樞鈕右方的記錄分別獨立地做排序 2019/8/20 演算法 ＿ 第五章

17 快速排序法 2019/8/20 演算法 ＿ 第五章

18 快速排序法 2019/8/20 演算法 ＿ 第五章

19 Procedure Quicksort(A, l, r) If l < r then s = Partition(A, l, r)
Quick Sort, Introduction to the Design & Analysis of Algorisms By A. Levitin Procedure Quicksort(A, l, r) If l < r then s = Partition(A, l, r) Quicksort(A, l, s-1) Quicksort(A, s+1, r) 2019/8/20 演算法 ＿ 第五章

20 Procedure Partition(A, l, r) // Hoare Partirion pivot = A[l] i = l;
Quick Sort, Introduction to the Design & Analysis of Algorisms By A. Levitin Procedure Partition(A, l, r) // Hoare Partirion pivot = A[l] i = l; j = r + 1 repeat repeat i = i + 1 while (until) A[i]  pivot repeat j = j - 1 while (until) A[j]  pivot swap(A[i], A[j]) until i  j swap(A[i], A[j]) // undo last swap when i  j swap(A[l], A[j]) return j 2019/8/20 演算法 ＿ 第五章

21 Quick Sort, Introduction to the Design & Analysis of Algorisms By A
Quick Sort, Introduction to the Design & Analysis of Algorisms By A. Levitin Pivot = A[i] i, left right j 2 8 7 1 3 5 6 4 Pivot = 2 left i right j A[i]  2 2 8 7 1 3 5 6 4 Pivot = 2 left i right j A[i]  2 2 8 7 1 3 5 6 4 2019/8/20 演算法 ＿ 第五章

22 Quick Sort, Introduction to the Design & Analysis of Algorisms By A
Quick Sort, Introduction to the Design & Analysis of Algorisms By A. Levitin Pivot = 2 left i right j A[i]  2 2 8 7 1 3 5 6 4 Pivot = 2 left i j, right A[j]  2 2 8 7 1 3 5 6 4 Swap(A[i], A[j]) Pivot = 2 left i j, right 2 8 7 4 3 5 6 1 2019/8/20 演算法 ＿ 第五章

23 Quick Sort, Introduction to the Design & Analysis of Algorisms By A
Quick Sort, Introduction to the Design & Analysis of Algorisms By A. Levitin Pivot = 2 left i j, right A[i]  2 2 8 7 4 3 5 6 1 Pivot = 2 left i j, right A[i]  2 2 8 7 4 3 5 6 1 Pivot = 2 left i j, right A[i]  2 2 8 7 4 3 5 6 1 2019/8/20 演算法 ＿ 第五章

24 Quick Sort, Introduction to the Design & Analysis of Algorisms By A
Quick Sort, Introduction to the Design & Analysis of Algorisms By A. Levitin Pivot = 2 left i, j, right A[i]  2 2 8 7 4 3 5 6 1 Pivot = 2 left j i, right A[j]  2 2 8 7 4 3 5 6 1 Swap(A[i], A[j]) Pivot = 2 left j i, right 2 8 7 4 3 5 1 6 2019/8/20 演算法 ＿ 第五章

25 Swap(A[i], A[j]) // undo last exchange
Quick Sort, Introduction to the Design & Analysis of Algorisms By A. Levitin Swap(A[i], A[j]) Pivot = 2 left j i, right 2 8 7 4 3 5 1 6 Swap(A[i], A[j]) // undo last exchange Pivot = 2 left j i, right 2 8 7 4 3 5 6 1 Swap(A[l], A[j]) Pivot = 2 left j i, right 6 8 7 4 3 5 2 1 2019/8/20 演算法 ＿ 第五章

26 快速排序法 W(n) = O(n2) 最佳情況時間複雜度是 O(n log n) 平均計算時間是 O(n log n) 2019/8/20
演算法 ＿ 第五章

27 快速排序法 歸納基礎：當n = 2，從 (5.1) 式得到Tavg(2) ≤ 2c + 2b ≤ kn loge2。
歸納假設：假設Tavg(n) ≤ kn loge n，其中1 ≤ n < m。 2019/8/20 演算法 ＿ 第五章

28 快速排序法 歸納步驟：從 (5.1) 式跟歸納假設中我們得到： 2019/8/20 演算法 ＿ 第五章

29 快速排序法 2019/8/20 演算法 ＿ 第五章

30 二維平面上的極點 給定平面上的兩個點 P1 = (x1, y1), P2 = (x2, y2)，我們說 P1 凌駕（dominate）P2 若且唯若 x1 > x2 且 y1 >y2 如果一個點不被任何點所凌駕，則我們就稱該點為極點（maximal point） 2019/8/20 演算法 ＿ 第五章

31 二維平面上的極點 2019/8/20 演算法 ＿ 第五章

32 二維平面上的極點 2019/8/20 演算法 ＿ 第五章

33 二維平面上的極點 2019/8/20 演算法 ＿ 第五章

34 二維平面上的極點 2019/8/20 演算法 ＿ 第五章

35 二維平面上的極點 2019/8/20 演算法 ＿ 第五章

36 二維平面上的極點 2019/8/20 演算法 ＿ 第五章

37 二維平面上的極點 步驟二裡的 2.1 行找中位數需要 O(n) 的時間，2.2行的分割也需要O(n) 的時間 步驟三需要 2T(n/2)
步驟四的 4.1 行求最大值需要 O(n) 的時間，4.2 行比較 SL 極點的 y 座標值與 ymax 需要 O(n) 的時間 因此，整個演算法的時間複雜度是 T(n) = 2T(n/2) + O(n) = O(n log n) 2019/8/20 演算法 ＿ 第五章

38 最接近的兩點 2019/8/20 演算法 ＿ 第五章

39 最接近的兩點 直接解這個問題需要計算任意兩點間的距離，因此我們需要 O(n2) 的時間才能解出這個問題
我們可以利用分而治之法將複雜度降到O(n log n) 2019/8/20 演算法 ＿ 第五章

40 最接近的兩點 2019/8/20 演算法 ＿ 第五章

41 最接近的兩點 2019/8/20 演算法 ＿ 第五章

42 最接近的兩點 2019/8/20 演算法 ＿ 第五章

43 最接近的兩點 我們只需要將RL裡的每一點與RR中頂多6個點配對、檢測即可 2019/8/20 演算法 ＿ 第五章

44 最接近的兩點 2019/8/20 演算法 ＿ 第五章

45 最接近的兩點 2019/8/20 演算法 ＿ 第五章

46 最接近的兩點 2019/8/20 演算法 ＿ 第五章

47 最接近的兩點 步驟一只需要 O(1) 的時間 步驟二的兩次排序分別都需要 O(n log n) 假設步驟三至步驟五的執行時間為 T(n)
步驟五裡的p點最壞情況下有n/2個，針對每一個p點我們頂多需要檢測六個在SR裡的點，因此步驟五的最壞情況複雜度為6cn = O(n)，其中c是一個常數 我們於是得到步驟三至步驟五的執行時間為 T(n) = 2T(n/2) + O(n) = O(n log n)。 2019/8/20 演算法 ＿ 第五章

48 快速傅利葉轉換 數位傅利葉轉換（DFT）的定義為： 它的逆轉換則定義為： 2019/8/20 演算法 ＿ 第五章

49 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

50 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

51 快速傅利葉轉換 利用wn，我們可以將傅利葉轉換重寫成 2019/8/20 演算法 ＿ 第五章

52 快速傅利葉轉換 當 n = 4 時： 2019/8/20 演算法 ＿ 第五章

53 快速傅利葉轉換 把偶數項放一起，奇數項放一起： 2019/8/20 演算法 ＿ 第五章

54 快速傅利葉轉換 但是， 2019/8/20 演算法 ＿ 第五章

55 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

56 快速傅利葉轉換 我們因此可以將上面的 4 點傅利葉轉換係數重寫成： 2019/8/20 演算法 ＿ 第五章

57 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

58 快速傅利葉轉換 8點傅利葉轉換 2019/8/20 演算法 ＿ 第五章

59 快速傅利葉轉換 把偶數點跟奇數點分別集中 2019/8/20 演算法 ＿ 第五章

60 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

61 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

62 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

63 快速傅利葉轉換 我們因此可以將上面的 8 點傅利葉轉換係數重寫成： 2019/8/20 演算法 ＿ 第五章

64 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

65 快速傅利葉轉換 n = 2k 點的傅利葉轉換 將 Aj 與 Aj+n/2 湊成一對 2019/8/20 演算法 ＿ 第五章

66 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

67 快速傅利葉轉換 定義 Bj 與 Cj 如下： 2019/8/20 演算法 ＿ 第五章

68 快速傅利葉轉換 2019/8/20 演算法 ＿ 第五章

69 快速傅利葉轉換 時間複雜度是 T(n) = 2T(n/2) + cn = O(n log n) 2019/8/20 演算法 ＿ 第五章