作者:
chz (稻草人騎士)
2014-10-15 18:31:28※ 引述《dreamoon (大笨蛋小月唷!)》之銘言：
: ※ 引述《DJWS (...)》之銘言：
: : 依序掃描n個中位數 O(n)
: : 比x小(大)的中位數
: : 其所對應的陣列，預計刪除小(大)的那一半
: : 也就是 low = (low + high) / 2 + 1; O(1)
: : (或者 high = (low + high) / 2 - 1;)
: : 預計更新陣列大小為 size = high - low + 1 O(1)
: : 累計欲刪除的元素數量 y (小的那些) O(1)
: : 如果第k個元素小於等於 y，那麼就刪除最大的那 1/4，下個回合找第 k 小的元素
: : 否則就刪除最小的那 1/4，下個回合找第 k = Σsize - y 大的元素
: 對於這裡我有點困惑
: 若k<=y，刪除叫大的那些數是沒問題的，因為那些數一定比第k個數還大
: 但是當k>y時，真的能刪除較小的那一部分嘛?
: 例如說現在有7*7的矩陣
: 1, 2, 3, 4, 5, 6, 7
: 8, 9,10,11,12,13,14
: 15,16,17,18,19,20,21
: 22,23,24,25,26,27,28
: 29,30,31,32,33,34,35
: 36,37,38,39,40,41,42
: 43,44,45,46,47,48,49
: 並且我要找的數是第17小的數
: 但比較小的那部分卻只有16個數
: 於是按照這個演算法我們就會把真正的第17小的數給移除了0.0(我沒理解錯的話...)
其實把DWJS的方法稍微改一下就可以了。
對於目前的n條序各列改中位數 O(1)
n個中位數找中位數(MoM) O(n)
對每一條序列用binary search找比MoM大和小各有多少個 O(n logn)
會有 n_l個比MoM小，n_r個比MoM大，選擇目標的那一邊。
更新序列的 head和 tail O(1)
看把n_l或n_r被砍掉的部份算到全部被移掉的N_L和N_R中。
重複以上動作直到MoM收斂。
這個動作至多進行 O(log n)次，分析如下：
考慮n條長度為n的序列
每次動作至少有n/2條會被移除一半
也就是說，至多只要 2 log n次，所有的序列都會只剩下一個元素。
因此在經過 O(n log n log n)的時間後,還剩下O(n)個元素要找第k大的數。
再加上最後的O(n)，時間複雜度還是 O(n log n log n)。
ps. 跑實驗的結果 random input大概只需要 log n個 iteration就會收斂了。
幾乎不會跑到 2 log n個iteration。