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

[JKLee (J.K.Lee)]

老師在上課時說，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
推 FRAXIS: 這兩種方法應該是一樣的 都會有兩個遞迴呼叫
推 FRAXIS: 所以你的遞迴式有問題..
→ can18: 為什麼1~3步可以獨立? 就是遞迴下去做啊
為何不能獨立出來?

→ can18: 還有你第一個的遞迴式也寫錯了吧
→ can18: 5個: T(n) = T(n/5) + T(7n/10) + O(n)
第一個遞迴式是參考林立宇的寫法，只是概算，不是精算，但不影響結果。

S_1  ˙˙˙˙˙     
     ─────     
     ˙˙˙˙˙     
     ─────     
     ˙˙＊˙˙     
     ─────     
     ˙˙˙˙˙     
     ─────     
     ˙˙        S_2

從圖可觀察到，S_2的大小至少有1/4*n。

因此去掉S_2後，最多剩下 3/4*n。

→ can18: 3個: T(n) = T(n/3) + T(2n/3) + O(n)
推 can18: 你知道你第二個的問題在哪嗎?
→ can18: 第三步是把 n/5 個數丟進 "原本" 的演算法
→ can18: 簡單的說 根本不存在你所謂的演算法G
→ can18: 有的話你直接用G求median就好了 不用那麼複雜
有啊。我不是第一個想到的。我也覺得這樣很複雜。

演算法筆記 - Sequence Manipulation
http://www.csie.ntnu.edu.tw/~u91029/SequenceManipulation.html
"Select in Array: Median-of-Medians Algorithm
...
時間複雜度O(N)"

→ nat99up: 你漏掉小堆中位數之間的selection
推 nat99up: 分三堆的話S-_1跟S_2的大小為1-(1/2 * 1/3 *2)
看來分3堆時，概算會出錯

→ nat99up: c大其實7/10跟3/4的版本都有
→ can18: 謝謝n大 抱歉 我不知道這個版本
推 can18: 不是啊 = = 你那個網站O(n)就是用分5堆的才得到啊           10/27 09:06
推 can18: 所以你直接用G求就好了啊 但實際上G就是分5堆
我應該是誤會你的意思了

→ can18: 所以你是想表面上分3堆 骨子用分5堆求然後宣稱分3堆可以O(n
→ can18: )嗎
調整推文順序，方便閱讀。

→ can18: 你有懂了嗎 還是我再講詳細一點
抱歉，收回前言，我還是不瞭解。


問題1.

把median of medians演算法獨立出來，

不管是5個一組，還是3個一組，我都算出費時O(n)。


問題2.

若我在問題1中的推導無誤，那麼改寫後的selection algo.，

不管是5個一組，還是3個一組，也都費時O(n)。


問題3.

若1.2.我都沒錯，那為什麼過去那些研究演算法的學者，

有什麼好理由不把median of medians演算法獨立出來?

→ nat99up: 我誤以為你的S1和S2是剩下來的n了 把1-拿掉
推 gary70812: 我認為你的G演算法如果是分三組“遞迴”下去的話，找出
→ gary70812: 的數對selected algorithm 是沒有幫助的，不管是三個一
→ gary70812: 組或五個一組都一樣，假設有十組5個數，共50個，五個一
→ gary70812: 組，你的遞迴最後會剩兩個數 這時候該挑哪個？挑哪個
→ gary70812: 都對原演算法沒有幫助，以上我的觀點，不一定對
為何兩個任一個都沒有幫助?

推 gary70812: 因為他不一定在中間，沒辦法保證下次只要算T(3/4*n)
一般會假設 n <= n_0 時，T(n_0) = Θ(1)，as n_0 is constant.

例如我已算出T(50)為常數時間，即T(50) = Θ(1)。

則只要 n<=50，T(n)都為Θ(1)。

推 gary70812: 嗯...那這樣你提出的方法就是O(n)了？還是你還有發現
→ gary70812: 哪裡有問題
推 can18: 其實最後一組剩幾個都沒差 頂多花常數時間BigO下會被去掉
→ can18: 原po的問題是 他所謂的G演算法必須架構在5個一堆下才能達O(
→ can18: n)
→ can18: 所以其實只有主程式是3個一堆 副程式都是5個一堆
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個以上一組。

以前那些大師怎麼可能沒想到，一定有什麼理由使他們不這麼做。
不然就是我算錯了。

推 FRAXIS: http://www.cs.uwm.edu/faculty/ad/select.pdf
哈。我知道問題出在哪裡了。

如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