[理工] 資結 演算法 median of medians selection algo.時間複雜度

看板Grad-ProbAsk作者 (J.K.Lee)時間8年前 (2017/10/27 02:37), 8年前編輯推噓10(10推 0噓 22→)
留言32則, 4人參與, 8年前最新討論串1/1
老師在上課時說，selection algorithm 中的 median of medians， 若改成3個3個一組，時間複雜度就會超過O(n)。 但我用的第二種方法卻無法得到這個結果，我哪裡出錯了? ==================================================== 第一種方法: 原本的遞迴關係式(5個5個一組)會從 T(n) = T(n/5) + T(3/4*n) + O(n) 變成 T(n) = T(n/3) + T(3/4*n) + O(n)。 新的T(n) = O(n^{1+log_{4/3}(13/12)})。比O(n)大。 ================================================ S_1 ˙˙˙˙˙ ───── ˙˙˙˙˙ ───── ˙˙＊˙˙ ───── ˙˙˙˙˙ ───── ˙˙ S_2 ================================================ 第二種方法: 以下參考自：林立宇 2006 演算法講義 p.37 【演算法 2-5】 The median of medians selection algorithm Select(A[size n],k) 1. 將input的n個數每5個一組，除了最後一組不足5個數，而是n mod 5個。 總共ceiling(n/5)組。 2. 將每組作sorting，並求得各組之median。 3. 將step 2得到的ceiling(n/5)個median當input，遞迴去求medians的median，p。 4. 從n個數中，收集小於與大於p的數，分別放入集合S_1與S_2。(見上圖) 5. 假設p為第x小的數。 若k=x，則return p； 若k<x，則去掉被S_2包含的數，再遞迴求剩餘數中第k小的數； 若k>x，則去掉被S_1包含的數，再遞迴求剩餘數中第k-|S_1|小的數。 ------------------------------------------------------------- 將上述算法中的第1步到第3步獨立出來， 變成一個利用median of medians來找median近似值的演算法G。 再將演算法G的5個一組改成3個一組。 演算法G的時間複雜度的遞迴關係式: T(n) = T(n/3) + O(n)； T(1) = 1。 演算法G的時間複雜度T(n) = O(n)。 selection algo.可改寫為新的演算法F: F(input size: n, k) { p = G(input size: n); // 找出中位數近似值，p。費時O(n)。 ...; // 算出p是n個數中，第幾小的數。假設p是第x小的數。費時O(n)。 if(k=x) return p; else if(k<x) { ...; // 去掉大於等於p的數。費時O(n)。 return F(input size: 3/4*n, k); } else if(k>x) { ...; // 去掉小於等於p的數。費時O(n)。 return F(input size: 3/4*n, k-|S_1|); } } 新演算法F的時間複雜度的遞迴關係式: T(n) = T(3/4*n) + O(n)； T(1) = 1。 演算法F的時間複雜度T(n) = O(n)。沒有超過O(n)!? ------------------------ 問題1. 把median of medians演算法獨立出來， 不管是5個一組，還是3個一組，我都算出費時O(n)。 問題2. 若我在問題1中的結果無誤，那麼改寫後的selection algo.， 不管是5個一組，還是3個一組，也都費時O(n)。 問題3. 若1.2.我都沒錯，那為什麼過去那些研究演算法的學者， 有什麼好理由不把median of medians演算法獨立出來? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.76.116 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1509043047.A.16A.html
推
10/27 08:11, 8年前 , 1F
這兩種方法應該是一樣的 都會有兩個遞迴呼叫
10/27 08:11, 1F
推
10/27 08:13, 8年前 , 2F
所以你的遞迴式有問題..
10/27 08:13, 2F
→
10/27 08:43, 8年前 , 3F
為什麼1~3步可以獨立? 就是遞迴下去做啊
10/27 08:43, 3F
為何不能獨立出來?
→
10/27 08:45, 8年前 , 4F
還有你第一個的遞迴式也寫錯了吧
10/27 08:45, 4F
→
10/27 08:46, 8年前 , 5F
5個: T(n) = T(n/5) + T(7n/10) + O(n)
10/27 08:46, 5F
第一個遞迴式是參考林立宇的寫法，只是概算，不是精算，但不影響結果。 S_1 ˙˙˙˙˙ ───── ˙˙˙˙˙ ───── ˙˙＊˙˙ ───── ˙˙˙˙˙ ───── ˙˙ S_2 從圖可觀察到，S_2的大小至少有1/4*n。 因此去掉S_2後，最多剩下 3/4*n。
→
10/27 08:48, 8年前 , 6F
3個: T(n) = T(n/3) + T(2n/3) + O(n)
10/27 08:48, 6F
推
10/27 08:55, 8年前 , 7F
你知道你第二個的問題在哪嗎?
10/27 08:55, 7F
→
10/27 08:56, 8年前 , 8F
第三步是把 n/5 個數丟進 "原本" 的演算法
10/27 08:56, 8F
→
10/27 08:57, 8年前 , 9F
簡單的說 根本不存在你所謂的演算法G
10/27 08:57, 9F
→
10/27 08:57, 8年前 , 10F
有的話你直接用G求median就好了 不用那麼複雜
10/27 08:57, 10F
有啊。我不是第一個想到的。我也覺得這樣很複雜。 演算法筆記 - Sequence Manipulation http://www.csie.ntnu.edu.tw/~u91029/SequenceManipulation.html "Select in Array: Median-of-Medians Algorithm ... 時間複雜度O(N)"
→
10/27 08:55, 8年前 , 11F
你漏掉小堆中位數之間的selection
10/27 08:55, 11F
推
10/27 08:59, 8年前 , 12F
分三堆的話S-_1跟S_2的大小為1-(1/2 * 1/3 *2)
10/27 08:59, 12F
看來分3堆時，概算會出錯
→
10/27 08:57, 8年前 , 13F
c大其實7/10跟3/4的版本都有
10/27 08:57, 13F
→
10/27 08:58, 8年前 , 14F
謝謝n大 抱歉 我不知道這個版本
10/27 08:58, 14F
推 can18: 不是啊 = = 你那個網站O(n)就是用分5堆的才得到啊 10/27 09:06
推
10/27 09:08, 8年前 , 15F
所以你直接用G求就好了啊 但實際上G就是分5堆
10/27 09:08, 15F
我應該是誤會你的意思了
→
10/27 09:09, 8年前 , 16F
所以你是想表面上分3堆 骨子用分5堆求然後宣稱分3堆可以O(n
10/27 09:09, 16F
→
10/27 09:09, 8年前 , 17F
)嗎
10/27 09:09, 17F
調整推文順序，方便閱讀。
→
10/27 09:28, 8年前 , 18F
你有懂了嗎 還是我再講詳細一點
10/27 09:28, 18F
抱歉，收回前言，我還是不瞭解。 問題1. 把median of medians演算法獨立出來， 不管是5個一組，還是3個一組，我都算出費時O(n)。 問題2. 若我在問題1中的推導無誤，那麼改寫後的selection algo.， 不管是5個一組，還是3個一組，也都費時O(n)。 問題3. 若1.2.我都沒錯，那為什麼過去那些研究演算法的學者， 有什麼好理由不把median of medians演算法獨立出來?
→
10/27 09:29, 8年前 , 19F
我誤以為你的S1和S2是剩下來的n了 把1-拿掉
10/27 09:29, 19F
推
10/27 13:18, 8年前 , 20F
我認為你的G演算法如果是分三組“遞迴”下去的話，找出
10/27 13:18, 20F
→
10/27 13:18, 8年前 , 21F
的數對selected algorithm 是沒有幫助的，不管是三個一
10/27 13:18, 21F
→
10/27 13:18, 8年前 , 22F
組或五個一組都一樣，假設有十組5個數，共50個，五個一
10/27 13:18, 22F
→
10/27 13:18, 8年前 , 23F
組，你的遞迴最後會剩兩個數 這時候該挑哪個？挑哪個
10/27 13:18, 23F
→
10/27 13:18, 8年前 , 24F
都對原演算法沒有幫助，以上我的觀點，不一定對
10/27 13:18, 24F
為何兩個任一個都沒有幫助?
推
10/27 13:29, 8年前 , 25F
因為他不一定在中間，沒辦法保證下次只要算T(3/4*n)
10/27 13:29, 25F
一般會假設 n <= n_0 時，T(n_0) = Θ(1)，as n_0 is constant. 例如我已算出T(50)為常數時間，即T(50) = Θ(1)。 則只要 n<=50，T(n)都為Θ(1)。
推
10/27 14:44, 8年前 , 26F
嗯...那這樣你提出的方法就是O(n)了？還是你還有發現
10/27 14:44, 26F
→
10/27 14:44, 8年前 , 27F
哪裡有問題
10/27 14:44, 27F
推
10/27 15:15, 8年前 , 28F
其實最後一組剩幾個都沒差 頂多花常數時間BigO下會被去掉
10/27 15:15, 28F
→
10/27 15:16, 8年前 , 29F
原po的問題是 他所謂的G演算法必須架構在5個一堆下才能達O(
10/27 15:16, 29F
→
10/27 15:16, 8年前 , 30F
n)
10/27 15:16, 30F
→
10/27 15:17, 8年前 , 31F
所以其實只有主程式是3個一堆 副程式都是5個一堆
10/27 15:17, 31F
C大可能誤會了。 我的意思是，把median of medians演算法獨立出來，變成演算法G。 再把演算法G放回修改後selection algo.，即演算法F。 不管是5個一組，還是3個一組，都是算出費時O(n)。 怎麼可能會有這麼好康的代誌? 程式變簡單了，各個函數只專注作自己的事。 G專做 partition (median of medians)，也就是找中位數近似值； F專做 selection，要 partition 時，只需 call G 就好。 不像原本的，selection 與 partition (median of medians) 攪和在一起。 受到的限制變小了，原本的必須5個以上一組才能在線性時間算完， 現在只要3個以上一組。 以前那些大師怎麼可能沒想到，一定有什麼理由使他們不這麼做。 不然就是我算錯了。
推
10/27 20:40, 8年前 , 32F
10/27 20:40, 32F
哈。我知道問題出在哪裡了。 如C大所言，根本不存在演算法G。 準確來說，應該是那個演算法G求出的並不是 median of medians， 不管是5個一組或是3個一組。 如下圖所示。 "P"為演算法G最後找到的pivot。 "◎"代表大於等於P。 "。"代表小於等於P。 小 │ 。│。│˙│。│。│˙│˙│˙│˙ │ 。│。│˙│。│Ｐ│◎│˙│◎│◎ ↓ ˙│˙│˙│˙│◎│◎│˙│◎│◎ 大 小 │ 。│。│˙ │ 。│Ｐ│◎ ↓ ˙│◎│◎ 大 看到F大提供的文件才想到。 感謝以上各位大大。 ※ 編輯: JKLee (111.248.76.116), 10/28/2017 02:07:35
‣ 更多 JKLee 的文章
文章代碼(AID): #1PyYjd5g (Grad-ProbAsk)