淘汰與搜尋法 4 2019/5/9 演算法 ＿ 第四章.

Presentation on theme: "淘汰與搜尋法 4 2019/5/9 演算法 ＿ 第四章."— Presentation transcript:

1 淘汰與搜尋法 4 2019/5/9 演算法 ＿ 第四章

2 什麼叫淘汰與搜尋法 每一回合的處理都把搜尋的範圍減少一個固定比例 分成三個主要步驟：
如果要處理的資料量已經夠少，那麼用直接的方式解決；否則，把輸入資料分解成至少兩個獨立的小集合 淘汰掉一定不存在我們要的解的集合 針對可能包含我們要的解的集合遞迴地做步驟(2)的處理直到可能包含我們要的解的集合已經小到可以用步驟(1)的直接處理 2019/5/9 演算法 ＿ 第四章

3 哪些問題適用淘汰與搜尋法？ 如果一個問題的輸入資料可以予以刪除一些而不會影響到我們最後要的解，那麼這個問題就有可能適合用淘汰與搜尋法
2019/5/9 演算法 ＿ 第四章

4 找劣幣問題 給定一個裝有 32 個硬幣的袋子，硬幣當中可能有一個是劣幣 不僅如此，我們還知道劣幣的重量比真幣輕
我們的工作是判斷袋子裡是不是有劣幣。如果有的話，找出它 2019/5/9 演算法 ＿ 第四章

5 找劣幣問題 比較簡單，我們已知劣幣是比較輕的 但是，可能都是真幣 2019/5/9 演算法 ＿ 第四章

6 找劣幣問題 2019/5/9 演算法 ＿ 第四章

7 找劣幣問題 2019/5/9 演算法 ＿ 第四章

8 找劣幣問題－更好的演算法 2019/5/9 演算法 ＿ 第四章

9 找劣幣問題－更好的演算法 2019/5/9 演算法 ＿ 第四章

10 找劣幣問題 複雜度 T(n) = T(n/2) + a = (T(n/4) + a) + a = (T(n/8) + a) + a +a =  = T(1) + alog2 n = b + alog2 n = O(log n) T(n) = T(n/3) + a = (T(n/9) + a) + a = (T(n/27) + a) + a +a =  = T(1) + alog3 n = b + alog3 n = O(log n) 2019/5/9 演算法 ＿ 第四章

11 二元搜尋 middle := (left + right)/2 ? 如果越大的值被搜尋的機率越高
2019/5/9 演算法 ＿ 第四章

12 選出第 k 小的元素 給定一個含有 n 個元素的陣列 a[n]，這個問題要我們找出第 k 小的元素
例如，[12, 4, 5, 4, 5, 10, 2, 20] 如果 k = 1，我們得傳回2 如果k = 8，我們得傳回8 如果k = 6，我們得傳回10 如果k = 2，我們得傳回4 2019/5/9 演算法 ＿ 第四章

13 選出第 k 小的元素 中位數：k = n/2 我們可以先將 n 個元素排序過，然後再取出 a[k]
這麼做的話，我們至少需要 O(n log n) 的時間，因為排序問題的複雜度下限是 (n log n) 我們以下要介紹的淘汰與搜尋法卻可以在 O(n) 的時間內就把這個問題解決掉 2019/5/9 演算法 ＿ 第四章

14 選出第 k 小的元素 假設我們隨意地從 S 中選出一個元素 v，利用 v 將集合 S 分割成三個子集合：小於 v 的元素、等於 v 的元素、以及大於 v 的元素 2019/5/9 演算法 ＿ 第四章

15 選出第 k 小的元素 由於SL+Sv= 5，我們所要的第 8 小元素因此是在 SR 裡，而且是 SR 裡的第 3小元素 一般的情況
2019/5/9 演算法 ＿ 第四章

16 選出第 k 小的元素 從 S 分割出 SL、Sv、SR 只需要 O(n) 的時間
但是，我們卻因此可以將搜尋範圍由原本的 S 縮小成 SL 或 SR 如何選擇 v？ 2019/5/9 演算法 ＿ 第四章

17 最差情況下的最佳化演算法 n = 25且a = [2, 6, 8, 1, 4, 9, 20, 6, 22, 11, 9, 8, 4, 3, 7, 8, 16, 11, 10, 8, 2, 14, 15, 1, 12] 先將這 25 個元素分成 5 組：[2, 6, 8, 1, 4]、[9, 20, 6, 22, 11]、[9, 8, 4, 3, 7]、[8, 16, 11, 10, 8]、與[2, 14, 15, 1, 12] 這五組數字的中位數分別是：4, 11, 7, 10, 12 再取這五個中位數 [4, 11, 7, 10, 12] 的中位數是：10 這便是我們所選擇的 v 值 SL = {2, 6, 8, 1, 4, 9, 6, 9, 8, 4, 3, 7, 8, 8, 2, 1}、Sv = {10}、而SR = {20, 22, 11, 16, 11, 14, 15, 12} 2019/5/9 演算法 ＿ 第四章

18 最差情況下的最佳化演算法 2019/5/9 演算法 ＿ 第四章

19 最差情況下的最佳化演算法 不管是小於等於 10 或是大於等於 10 的虛線方形裡的元素個數都至少是S的1/4
何況沒框起來的元素也有可能小於等於（或大於等於）10 因此，不管我們是要淘汰掉 Sv 與 SR 或者 SL 與Sv，我們用中位數的中位數所選擇出的 v 值保證我們至少可以淘汰掉 ¼ 的元素 2019/5/9 演算法 ＿ 第四章

20 最差情況下的最佳化演算法 2019/5/9 演算法 ＿ 第四章

21 最差情況下的最佳化演算法 2019/5/9 演算法 ＿ 第四章

22 最差情況下的最佳化演算法 2019/5/9 演算法 ＿ 第四章

23 最差情況下的最佳化演算法 令 T(n) 表示執行 Select1(a, k, 1, n) 所需要的時間，則 其中 a, b, c 都是常數
利用歸納法很容易就可以證明 T(n)  20an, n  1，即 T(n) = O(n) 2019/5/9 演算法 ＿ 第四章

24 平均情況下的最佳化演算法 從 a[low:high] 中隨機選擇一個做為 v 值
最壞情況複雜度因此將是 n + (n-1) + (n-2) +  + (n-k) = O(n2) 但是，這種情況發生的機率實在是很低 同樣也是發生機率很低的是我們每一次都選到最好的元素，剛好使得SL, SR n/2 在這種情況下，T(n) = T(n/2) + an = O(n) 2019/5/9 演算法 ＿ 第四章

25 平均情況下的最佳化演算法 平均情況的複雜度會介於最佳情況的 O(n) 與最壞情況的 O(n2) 之間
2019/5/9 演算法 ＿ 第四章

26 平均情況下的最佳化演算法 隨機選擇一個 v 值它是介於第 25% ~ 75% 之間的機率是0.5
2019/5/9 演算法 ＿ 第四章

27 平均情況下的最佳化演算法 因此，平均起來我們做兩次分割後可以淘汰掉至少S/4 T(n)  T(3n/4) + O(n) = O(n)
2019/5/9 演算法 ＿ 第四章

28 平均情況下的最佳化演算法 2019/5/9 演算法 ＿ 第四章