關于元素選擇問題的總結

轉載自：算法：元素選擇問題總結

注：中位數：中間大小的數；上取整用| |表示，下取整用[ ]表示

類型1．選最大

輸入：n個不等的數

輸出：max

算法1 Findmax

1. max←L[1]

2. for i←2 to lenth[L]

do if max < L[i]

then max←L[i]

3. return max

算法最壞情況下的時間複雜性為O(n)

結論：在n 個數的數組中找最大的數, 并以比較作為基本運算的算法類中的任何算法最壞情況下至少要做n－1 次比較.

證: 因為MAX是唯一的, 其它的n－1個數必須在比較後被淘汰. 一次比較至多淘汰一個數,是以至少需要n－1 次比較.

結論: findmax 算法是最優算法.

類型2．找最大和最小

通常算法：順序比較

複雜性：W(n)=2n-2

算法2 FindMaxMin

1．将n個元素兩兩一組分成 [n/2] 組

2．每組比較，得到 [n/2] 個較小和 [n/2] 個較大

3．在 [n/2] 個 (n為奇數，是 [n/2] +1)較小中找最小min

4．在 [n/2] 個(n為奇數，是 [n/2] +1)較大中找最大max

複雜性：行2 比較 [n/2] 次，行3-4比較至多2*|n/2| -2次，

W(n)= [n/2] +2 |n/2| -2=n+ |n/2| -2 = |3n/2| -2

類型3．找第二大

通常算法：順序比較

1．順序比較找到最大max;

2．從剩下的n-1個數中找最大，即第二大second

複雜性：W(n)=n-1+n-2=2n-3

算法3：錦标賽方法 改進的方法，最優

1．k←n

2．将k個元素兩兩一組，分成 k/2 組

3．每組的2個數比較，找到較大的數

4．将被淘汰的較小的數在淘汰它的數所指向的連結清單中做記錄

5．if k為奇數then k← k/2 +1

6． else k← k/2

7．if k>1 then goto 2

8．max←最大數

9．second←max的連結清單中的最大

複雜性：

W(n)=n-1+ log n -1= n+ log n -2

類型4．一般性選擇問題

輸入：數組L, L的長度n, 正整數k, 1≤ k≤ n.

輸出：第k小的數

通常算法

1．排序

2．找第k小的數

時間複雜性：O(nlogn)

算法4 Select(S,k) 改進的算法

1．将S劃分成5個一組， 共nM= [n/5] 個組

2．每組找中位數，nM個中位數放到集合M

3．m*←Select(M, |M|/2 ) 将S中的數劃分成A,B,C,D四個集合

4．把A和D中的每個元素與m*比較，小的構成S1, 大的構成S2

5．S1←S1∪C; S2←S2∪B

6．if k =|S1|+1 then 輸出m*

7．else if k≤|S1|

8．         then Select(S1,k)

9. else Select(S2,k-|S1|-1)

複雜性估計 更詳細的請參考王曉東的《計算機算法設計與分析》（第2版） 電子工業出版社 P24-26

複雜性：W(n)=O(n)

行2： O(n)

行3： W(n/5)

行4： O(n)

行8-9: O(n)

類型5.一道綜合應用題

給定n個不同數的集合S和正整數i, i

算法A：調用i 次找最大算法findmax , 每調用一次從S中删除一個最大的數。

算法B：對S 排序，并輸出S 中最大的i 個數。

問：（1）分析A,B 兩個算法在最壞情況下的時間複雜性。

（2）試設計一個最壞情況下時間複雜性的階更低的算法。要求用文字說明算法的設計思想；簡要給出算法的僞碼描述（可以調用學過的算法，對于使用的變量或過程要給與說明，不要求寫程式）；分析算法最壞情況下的時間複雜性。

解：

（1）算法A: i*n=O（n3/2）(3/2次方）

算法B:n*logn

（2）關于算法5的說明：

設k 表示第i 大元素在排好序數組的下标，元素記為x;

用選擇算法确定這個元素x，

用x 劃分數組S, 将比x 大的放到後邊；

排序S 中從k 到n 的元素，倒序輸出。

算法5

輸入: 集合S

輸出：S 中最大的i 個數

1. k←n-i+1;

2. x←Select(S, n, k);

3. 用x劃分S，将S 中比x 大的元素放到數組的k +1到n的位置；

4. 排序S[k..n]

5. 倒序輸出

複雜度：O(n)+O(i*logi)

參考文檔：北大計算機屈婉玲老師的教學課件和王曉東的《計算機算法設計與分析》（第2版）

轉載于:https://blog.51cto.com/dongdong1314/401219