推 nowar100:推swon大 真強者! 10/18 02:49
推 afulist:解答真是太詳細了~ 10/18 08:02
※ 引述《afulist (亞弗利斯特)》之銘言：
: Consider the problem: Give a sequence S=X1,X2,.....,Xn of element and an
: integer k, where 1<=k<=n, find the kth-smallest element in S.
: (a)Give a linear-time worst case algorithm for solving this problem
選第 k 大的值利用 Median of Medians 的方式 (Prune and Search)
Input：Sequence S, k
Output：kth-smallest element
(Step 1) 將 n 個元素分成 n/r 群(取天花板)，每群 r 個，不足 r 個補上無限大
(此處考慮 n>=r ，如果 n < r 時就用 Brute-Force Method 即可，r 為常數)
(Step 2) 將 n/r 群分別進行排序
(Step 3) 先取出 n/r 群的各個中位數，再取出這些 n/r 個中位數的中位數
(Median of Medians) 簡稱 MM
(Step 4) 利用 MM 進行 Partition 動作，將 S Sequence 分成三個 Subset
S1(<MM 的元素)、S2(=MM 的元素)、S3(> MM的元素)
(Step 5) If (k <=|S1|) 在 S1 中遞迴尋找
ElseIf k<=|S1|+|S2| 即 MM
Else 在 S3 中遞迴尋找
通常取 r = 5 做處理，下面就取 r = 5 時來做分析
: (b)Analyze the complexity of your algorithm in (a).
令 T(n) 為其時間函數
(Step 1) 掃描整個序列一遍 => O(n)
(Step 2) 排序需要 n/5 * O(5log5) = O(n)
(Step 3) 取出 n/r 個數的中位數需要 T(n/r) => T(n/5)
(Step 4) Partition 再掃描整個序列一遍 => O(n)
(Step 5) 遞迴處理 ==> T(3/4n)
以下圖為例假設有 25 個元素，取 r = 5 做完 Step 1~4 的情形如下
其中 x 以左都代表群中小於等於 x 的元素 (因為 x 為中位數)
x 以右都代表群中大於等於 x 的元素
--------------
第一群 | o o x | o o
| |
第二群 | o o x | o o
| -----|---------
第三群 | o o | MM | o o |
-------------- |
第四群 o o | x o o |
| |
第五群 o o | x o o |
---------------
假定我們要尋找的 k-th element 落在 S1(< MM 元素)
則我們至少可以過慮掉右下方格裡的這些元素
同理，如果落在 S3 我們至少可以過慮掉左上方格裡的這些元素
總之，最差可以過慮掉 n/4 個元素，再遞迴處理剩下四分之三 n 的元素
===> 所以尚需 T(3/4 n) 的時間進行遞迴處理
故 T(n) = O(1) , n <= 5
而 T(n) = T(n/5) + T(3/4 n) + O(n), n > 5
(方法 1) 利用 Recursive Tree：1/5+3/4 < 1 => T(n) = O(n)
(方法 2) T(n) = T(n/5) + T(3/4 n) + O(n)
<= 2T(3/4 n) + O(n)
log 2
4/3
以 Master Method n < n => T(n) = O(n)
(方法 3) By Induction, 假設 T(n) <= 20nc 成立
當 n<=5 時，T(n) <= 20nc = C => 成立
假設 n < k 時 T(k) <= 20 kc 成立
考慮 n = k 時
T(k) = T(k/5) + T(3/4 k) + O(k)
<= 20c(k/5) + 20c(3/4 k) + ck
= 4kc + 15kc + kc = 20 kc
故 T(n) <= 20nc 成立 => T(n) = O(n)
註：如果 Quick Sort 運用此 Select k-th smallest element 方式
選擇第 n/2 大的元素來當作 Partition 的 Pivot
此時 Quick Sort 即使在 Worst Case 依舊可以是 O(nlogn)
但通常考試都還是以 Worst Case 為 O(n^2)
: 這題要線性時間找第K個元素
: 請問要用哪個演算法呢?感謝高手解答
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.54.212