開頭廢話
這個問題是Donald.E.Knuth在他發表的論文Mathematical Analysis of Algorithms中提到的，這里對他的演算法分析程序給出了更詳細的解釋，
問題描述：
給定一個陣列a[1,2,...,n]，用盡量少的比較次數找出陣列中第t大的數，（假定這n個數兩兩不同），
演算法描述：
對于這個問題，可以很容易想到對應的演算法，一個 \(O(n\log n)\) 的排序演算法總能解決問題（然鵝今天我們并不對陣列進行完全的排序），
參照快速排序中的Partition操作，將元素a[i]放到某個位置\(k\)，使得排在它前面的元素都比它大（但不一定按照從大到小的次序排列），后面的元素都比它小，再根據a[i]的位置\(k\)與\(t\)的大小關系，縮小查找范圍再對子問題求解，
對于每一次Partition操作，會有這樣的3種情況：
(1).若\(k=t\)，演算法結束，
(2).若\(k>t\)，則對a[i]~a[k-1]遞回地求解
(3).若\(k<t\)，則對a[k+1]~a[j]遞回地求解
時間復雜度分析
在這個問題的求解程序中，產生子問題的規模不斷縮小，其中影響子問題的變數有\(n\)（陣列的長度）和\(t\)（待查找的t），Knuth記\(C_{n,t}\)為在\(n\)個元素的陣列中選擇第\(t\)大的數所需的平均比較次數，這里有一個前提，我們假設陣列的排列是隨機的，每一次Partition找到第1，第2，...，第n大的數概率均為\(\frac 1 n\)，
于是我們可以得到這樣的式子：
\[\begin {aligned} C_{1,1}&=0\\ C_{n,t}&=n-1+\frac 1n (A_{n,t}+B_{n,t}+0) \end {aligned} \]
其中\(A_{n,t}\)和\(B_{n,t}\)的定義如下：
\[\begin {aligned} A_{n,t}&=C_{n-1,t-1}+C_{n-2,t-2}+\cdots+C_{n-t+1,1}\\ B_{n,t}&=C_{t,t}+C_{t+1,t}+\cdots+C_{n-1,t} \end {aligned} \]
這里\(A_{n,t}\)對應的是遞回程序中所有\(k<t\)的情況，對于這些情況，我們從陣列的第\(k+1\)項開始向后的部分進行求解，如果把這部分看作一個新的陣列，那么原始陣列中第\(t\)大的數，在新的陣列中是第\(t-k\)大的，也就是說這部分子問題是查找長度為\(n-k\)的陣列中第\(t-k\)大的元素，其中\(1\leq k \leq n.\)
類似的，\(B_{n,t}\)對應所有\(k>t\)的情況，將陣列第一項到第\(k-1\)項取出，看作一個新的陣列，原始陣列中第\(t\)大的數，在這新的陣列中仍然是第\(t\)大，所以這部分的子問題是在長度為\(k-1\)的陣列中選擇第\(t\)大的數，其中\(t+1\leq k \leq n.\)
括號內剩下的一項\(0\)，對應的是\(k=t\)的情況，因為此時演算法結束，不需要再求解子問題，所以比較次數為\(0.\)括號外的\(n-1\)是一次Partition要進行的比較次數，
這樣，括號內就等于所有可能規模子問題的比較次數的總和，將它乘以\(\frac 1n\)，就得到子問題比較次數的數學期望，即我們所求的平均情況下的預期比較次數，
通過觀察我們可以得到以下的遞推公式：
\[\begin {aligned} A_{n+1,t+1}&=C_{n-1,t-1}+C_{n-2,t-2}+\cdots+C_{n-t+1,1}+C_{n,t}=A_{n,t}+C_{n,t}\\ B_{n+1,t}&=C_{t,t}+C_{t+1,t}+\cdots+C_{n-1,t}+C_{n+1-1,t}=B_{n,t}+C_{n,t} \end{aligned} \]
由上述等式作差消法，可以得到：
\[(n+1)C_{n+1,t+1}-nC_{n,t+1}-nC_{n,t}+(n-1)C_{n-1,t}\\ =(n+1)n-n(n-1)-n(n-1)+(n-1)(n-2)\\+(A_{n+1,t+1}-A_{n,t})-(A_{n,t+1}-A_{n-1,t})+(B_{n+1,t+1}-B_{n,t+1})-(B_{n,t}-B_{n-1,t}) \\ =2+C_{n,t}-C_{n-1,t}+C_{n,t+1}-C_{n-1,t} \]
合并同類項即可得到：
\[(n+1)C_{n+1,t+1}-(n+1)C_{n,t+1}-(n+1)C_{n,t}+(n+1)C_{n-1,t}=2\\\Downarrow\\ C_{n+1,t+1}-C_{n,t+1}-C_{n,t}+C_{n-1,t}=\frac{2}{n+1} \]
接下來我們考察邊界條件，當\(t=1\)時，由以上的式子我們可以得到下述方程組：
\[\left\{ \begin{array}{l} C_{n,1}= n-1+\frac{1}{n}(C_{1,1}+C_{2,1}+\cdots +C_{n-1,1})\\ B_{n,1}=C_{1,1}+C_{2,1}+\cdots+C_{n-1,1}\\ B_{n+1,1}=B_{n,1}+C_{n,1}\\ C_{n,1}=n-1+\frac{1}{n}(B_{n,1})\\ C_{n+1,1}=n+\frac{1}{n+1}(B_{n+1,1}) \end{array} \right. \]
消去方程組中包含\(B\)的項，可以得到：
\[\begin{aligned} (n+1)C_{n+1,1}-nC_{n,1} &= (n+1)n-n(n-1)+C_{n,1}\\ C_{n+1,1}-C_{n,1}&=2-\frac{2}{n+1} \quad\quad(*) \end{aligned} \]
接下來求解\(C_{n,1}\):
列出方程組：
\[\left\{ \begin{array}{c} \begin{aligned} C_{1,1}&=0\\ C_{2,1}-C_{1,1}&=2-\frac22\\ C_{3,1}-C_{2,1}&=2-\frac23\\ \cdots\\ C_{n,1}-C_{n-1,1}&=2-\frac2n\\ \end{aligned} \end{array} \right.\\ \]
將以上\(n\)個方程求和，最終左邊只剩下\(C_{n,1}\)，得到如下式子：
\[\begin{aligned} C_{n,1}&=2(n-1)-2\sum_{k=2}^n \frac1k\\ \quad\Downarrow \\ C_{n,1}&=2n-2\sum_{k=1}^n\frac1k=2n-2H_n \end{aligned} \]
這里的\(H_n\)表示調和級數的前\(n\)項部分和，
由于問題具有的對稱性（這部分可自行證明），\(C_{n,n}=C_{n,1}=2n-2H_n\)，將此式記作\((\Delta)\)，
由\((*)\)式，可以列出以下方程組：
\[\left\{ \begin{array}{l} (C_{n+1,t+1}-C_{n,t})-(C_{n,t+1}-C_{n-1,t})=\frac2{n+1}\\ (C_{n,t+1}-C_{n-1,t})-(C_{n-1,t+1}-C_{n-2,t})=\frac2{n}\\ \quad\quad\quad\quad\quad\quad\quad\quad\cdots\\ (C_{t+2,t+1}-C_{t+1,t})-(C_{t+1,t+1}-C_{t,t})=\frac2{t+2}\\ \end{array} \right.\\ \]
再次對這\(n-t\)個方程累加，并聯立\((\Delta)\)式，可以得到：
\[\begin{aligned} C_{n+1,t+1}-C_{n,t}&=\frac{2}{n+1}+\frac{2}{n}+\cdots+\frac{2}{t+2}+C_{t+1,t+1}-C_{t,t}\\ &=2(H_{n+1}-H_{t+1})+2-\frac{2}{t+1} \end{aligned} \]
依次寫出\(C_{n,t}-C_{n-1,t-1}\)到\(C_{2,2}-C_{1,1}\)的\(n-1\)個方程并再次累加（程序略去），可以推出：
\[C_{n,t}=2\sum_{2\leq k\leq t}(H_{n-t+k}-H_{k}+1-\frac1k)+C_{n+1-t,1} \]
化簡后：
\[C_{n,t}=2((n+1)H_n-(n+3-t)H_{n+1-t}-(t+2)H_t+n+3),\quad(1\leq t\leq n) \]
由于\(t\)與\(n\)同階，且平均情況下\(t\)的數學期望\(E(t)=\frac 2n\)，又 \(H_n=\Theta(\log n)\) ，所以：
\[C_{n,t}=O(n\log n) \]
至此，時間復雜度的證明結束，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73580.html
標籤：其他
上一篇：線性表 王炸篇 上