1.1選最大

選擇演算法
統一描述：設L是n個演算法的集合，從L中選出第k小的元素，1<=k<=n，當L中元素按從小到大排好序后，排在第k個位置的數，就是第k小的數，
下面介紹順序比較法
演算法Findmax
輸入：n個數的陣列L
輸出：max，k

max <- L[1]; k <- 1
for i <- 2 to n do      //for回圈執行n-1次
    if max < L[i]
    then max <- L[i]
         k <- i
return max, k

演算法Findmax第二行，for回圈執行n-1次，所以 \(W(n)=n-1\)
這個演算法是選最大問題在時間上最優的演算法（對于選最小問題，只需對演算法稍加改動，就可以得到順序比較的Findmin演算法）

1.2同時選最大和最小的演算法

設計思想：先選最大，然后把最大的從L中洗掉，接著選最小，
演算法：(利用Findmax和Findmin)
輸入：n個數的陣列L
輸出：max，min

if n=1 then return L[1]作為max和min
else Findmax
    從L中洗掉max
    Findmin

演算法執行的比較次數：\(W(n)=n-1+n-2=2n-3\)

分組比賽的方法
基本思想：首先將L中的元素兩兩一組，分成\(\lfloor n/2 \rfloor\)組（當n是奇數時有一個元素輪空），每組中的2個元素進行比較，得到組內較大和較少數，把至多\(\lfloor n/2 \rfloor + 1\)（當n為奇數時，把被輪空的元素加進來）個小組中較大的元素放在一起，運行Findmax，得到L中的最大元素，同理得到L中的最小元素，
演算法FindMaxMin

將n個元素兩兩一組分成n/2(下取整)組
每組比較，得到n/2(下取整)個較小和n/2(下取整)個較大的數      //比較n/2(下取整)次
在n/2(下取整)個（n為奇數時，是n/2(下取整)+1）較小中找最小min
在n/2(下取整)個（n為奇數時，是n/2(下取整)+1）較大中找最大max

行3和行4都執行\(\lceil n/2 \rceil -1\)次
所以\(W(n)=\lfloor n/2 \rfloor +2 \lceil n/2 \rceil-2=n+\lceil n/2 \rceil-2=\lceil 3n/2 \rceil-2\)
此演算法效率更高，是所有同時找最大和最小演算法中事件復雜度最低的演算法，

1.3找第二大

2次呼叫Findmax演算法
\(W(n)=n-1+n-2=2n-3\)

錦標賽演算法
把陣列中的元素兩兩一組，劃分為\(\lfloor n/2 \rfloor\)組（n為奇數時1個元素輪空），每組組內兩個元素比大小，大的進入下一輪（n為奇數時，輪空的元素也進入下一輪），
所以下一輪有\(\lceil n/2 \rceil\)個元素，繼續每組組內比大小，然后大的進入下一輪，直至找出max，篩掉\(n-1\)個元素，比較\(n-1\)次，

找第二大，不可能再用Findmax了，如果用Findmax，就又比較n-2次了，和上面的演算法兩次呼叫Findmax一樣，
所以，我們可以利用找max時比較所產生的記錄幫我們減少比較次數，在比賽前為每個元素設定一個指標，指向一個鏈表，把比較后比它小的元素都記錄進它的鏈表中，找出max后，在max的鏈表中用Findmax找出整個陣列第二大的元素，
演算法FindSecond
輸入：n個數的陣列L
輸出：second

k <- n
將k個元素兩兩一組，分成k/2(下取整)組
每組的兩個數比較，找到較大的
將被淘汰的較小的數在淘汰它的數所指向的鏈表中做記錄
if k為奇數 then k <- k/2(下取整)+1
           else k <- k/2(下取整)
if k>1 then goto 2
max <- 剩下的一個數
second <- max的鏈表中的最大

此時，第一輪兩兩比較的比較次數是\(n-1\)，但還不知道max的鏈表中有多少個元素，
所以接下來求解max所淘汰掉的元素個數（這部分的作業量）
設本輪參與比較的有\(t\)個元素，經過分組淘汰后進入下一輪的元素數至多是\(\lceil t/2 \rceil\)，下下一輪就是\(\lceil \lceil t/2 \rceil /2 \rceil = \lceil t/2^2 \rceil\)，
假設k輪淘汰后只剩max，則\(\lceil n/2^k \rceil = 1\).
若\(n=2^d\)，那么\(k=d=logn=\lceil logn \rceil\)
所以max進行了\(d\)次比較，\(W(n)=n-1+\lceil logn \rceil\)，
對于找第二大的問題，演算法Findmax是時間復雜度最低的演算法，

上面，我們只討論了一些特例情況，基本上使用順序比較或分組比較的方法，沒有明確的分治演算法的特征，下面考慮一般性的選第k小問題的演算法，用到分治策略，

2選第k小

輸入：陣列S，S的長度n，正整數k，1<=k<=n
輸出：第k小的數
選第k小，可以使用排序演算法，從小到大排好序后，選擇第k個即可，最好的排序演算法的時間復雜度是\(O(nlogn)\)，
下面考慮性能更好的分治演算法，就是\(O(n)\)時間的演算法，方便起見，假設陣列S中元素彼此不等，
以S中的某個元素\(m^*\)作為劃分標準，將S劃分為兩個子陣列S1和S2，把這個陣列中比\(m^*\)小的都放入\(S_1\)的陣列中，陣列\(S_1\)的元素個數是\(|S_1|\)個；把這個陣列中比\(m^*\)大的都放入\(S_2\)的陣列中，陣列\(S_2\)的元素個數是\(|S_2|\)個，

若\(k<|S_1|\)，則原問題歸納為在陣列\(S_1\)中找第\(k\)小的子問題，
若\(k=|S_1|+1\)，則\(m^*\)就是要找的第\(k\)小元素，
若\(k>|S_1|+1\)，則原問題歸納為在陣列\(S_2\)中找第\(n-|S_1|-1\)小的子問題，
演算法的關鍵是如何確定這個劃分\(S\)的標準\(m^*\)，它要具有以下特征：

尋找\(m^*\)的時間代價不能高于\(O(nlogn)\)，如果直接尋找\(m^*\)，時間應是\(O(n)\)，設選擇演算法的時間復雜度為\(T(n)\)，遞回呼叫這個演算法在\(S\)上的一個真子集M上尋找\(m^*\)，應該使用\(T(cn)\)時間（\(c<1\)，反映\(M\)的規模小于\(S\)）
通過\(m^*\)劃分的兩個子問題的大小分別記作\(|S_1|\)和\(|S_2|\)，每次遞回呼叫時，子問題規模與原問題規模\(n\)的比都不超過\(d\)（\(d<1\)），呼叫時間\(T(dn)\)，并且應保證\(c+d<1\)，否則方程\(T(n)=T(cn)+T(dn)+O(n)\)的解不會達到\(O(n)\)，
下面的分治演算法采用遞回呼叫的方法尋找\(m^*\)，先將\(S\)分組，5個元素一組，共分成\(\lceil n/5 \rceil\)個組，在每組中取中位數，把這\(\lceil n/5 \rceil\)個中位數放入集合\(M\)中，然后使用選擇演算法選出集合\(M\)中的中位數\(m^*\)，這次遞回呼叫的子問題規模是原問題規模的\(1/5\),\(1/5\)即為上文的特征(1)的\(c\)，
演算法Select(S,k)
輸入：陣列S，S的長度n，正整數k，1<=k<=n
輸出：第k小的數

將S劃分成5個一組，共n/5(上取整)個組
每組中找一個中位數，把這些中位數放到集合M中
m* <- Select(M,|M|/2)                  //選M中的中位數m*，將S中的陣列劃分成A,B,C,D四個集合
把A和D中的每個元素與m*比較，小的構成S1，大的構成S2
S1 <- S1并C ； S2 <- S2并B
if k=|S1|+1 then 輸出m*
else if k<=|S1|
    then Select(S1,k)
    else Select(S2,k-|S1|-1)

左下方的集合\(C\)中所以元素全部小于\(m^*\)，右上角的集合B中的所有元素全部大于\(m^*\)，僅僅對于\(A\)，\(D\)中的元素，我們不能確定它們是否大于或小于\(m^*\)，所以在演算法的行4加以比較，完成\(S1\)和\(S2\)的劃分，
下面分析時間復雜度
假設n是5的倍數，且\(n/5是奇數\)，即\(n/5=2r+1\)
所以\(|A|=|D|=2r\)，\(|B|=|C|=3r+2\)，\(n=10r+5\)，
若A，D的元素都小于\(m^*\)，那么它們都加入至S1中，且下一步演算法又在這個子問題上遞回呼叫，這對應了歸約后子問題的規模的上界，也正好是時間復雜度最壞的情況，類似的，如果A，D的元素都大于\(m^*\)，也會出現類似的情況，
以前者為例時，子問題的大小是
\(|A|+|C|+|D|=7r+2=7\frac{n-5}{10}+2=7\frac{n}{10}-1.5<\frac{7n}{10}\)
上式表明子問題規模最大不超過原問題的\(7/10\)，這個引數\(7/10\)就是前文特征(2)中的\(d\)，
所以最壞情況下的時間復雜度的遞推式：
\(W(n)<=W(\frac{n}{5})+W(\frac{7n}{10})+cn\)

\[\begin{aligned} W(n) & <= tn+0.9tn+0.9^2 tn+... \\ & = tn(1+0.9+0.9^2+...) \\ & = O(n) \end{aligned} \]

所以從上面的分析可以看出，這樣找的\(m^*\)完全滿足演算法要求，兩次遞回呼叫的引數分別是\(c=0.2\)，\(d=0.7\)，\(c+d=0.9<1\)，
所以Select演算法可以把時間復雜度降至線性時間，
分組時也可以選\(3\)個或\(7\)個元素，元素數的改變可能會改變\(m^*\)的特征，從而使得針對某些分組方法得到的\(c+d\)的值不再小于\(1\)，這就會增加運算時間，

求解選擇問題的時間復雜度最低的演算法就是O(n)時間的演算法！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67587.html

標籤：其他

上一篇：資料結構（二）：鏈表

下一篇：牛客練習賽60 A—F題解（缺E題）

分治策略 - 典型實體 - 選擇問題

1.1選最大

1.2同時選最大和最小的演算法

1.3找第二大

2選第k小

求解選擇問題的時間復雜度最低的演算法就是O(n)時間的演算法！