問題描述
把數列\((x_1,x_2,\cdots,x_n)\)變換順序為\((x_{p(1)},x_{p(2)},\cdots,x_{p(n)})\)，其中\(p\)是\(A=\{1,2,3,\cdots,n\}\)的一個排列，要求只使用\(O(1)\)的額外空間，例如，當數列為\((10,20,30,40)\),\(p\)為\((3,1,2,4)\)時得到的數列是\((30,10,20,40)\).
演算法描述
對于映射\(p:A\rightarrow A\)，它的含義是“排列后的陣列每個元素從哪里來”，即：變換后，陣列下標\(k\)處的數從變換前的下標\(p(k)\)處來，變換后下標為\(p(k)\)處的數從變換前下標為\(p(p(k))\)處的數來……因此我們可以把這條變換的鏈記為：
\[k\leftarrow p(k)\leftarrow p(p(k))\leftarrow \cdots \]
每一個下標都在唯一的一個“圈”內（原文這里的用詞為"cycle"），舉個例子：
對于給定的一個排列：
\[p=(8,2,7,1,6,9,3,4,5) \]
我們可以觀察到這樣的規律：
\[\left\{\begin{array}{l}p(1)=8,p(8)=4,p(4)=1\\p(2)=2\\p(3)=7,p(7)=3\\p(5)=6,p(6)=9,p(9)=5\end{array}\right. \]
對于括號中的每一行，最后一個等式右側的數在\(p\)映射下的像，等于第一個等式左側\(p\)作用的原像，對于每一個這樣的圈，我們都能用大小為\(O(1)\)的額外空間完成數字的交換，而這個交換我們從每個圈中的最小數開始做，
代碼描述：
for (int j = 1;j <= n;j++) {
int k = p(j);//n
while (k > j) {//n+a
k = p (k);//a
}
if(k == j) {
int y = x[j],l = p[k];//b
while (l != j) {//b+c
x[k] = x[l];//c
k = l;//c
l = p(k);//c
}
x[k] = y;//b
}
}
/*
這里b是變換p中"圈"的個數,c+b=n
a的含義是：對于每個j，在j所在的圈中第一個不大于j的數k距離p(j)的距離之和
*/
最壞情況
最壞的情況如下
\[p=(2,3,\cdots,n,1)\\a=(n-1)+(n-2)+\cdots +0=\frac{n^2-n}{2}\\b=1 \]
此為\(a\)的最壞情況和\(b\)的最好情況，
\[p=(1,2,\cdots,n-1,n)\\a=0\\b=n \]
此為\(a\)的最好情況和\(b\)的最壞情況，
b的平均值分析
對于上面參考的\(p\)的實體：
\[p=(8,2,7,1,6,9,3,4,5) \]
把所有的圈按照下述規則排列
1.圈內最小的數排在第一
2.圈內最小的數較大的，排在前面
則以上的\(p\)將變為\((5,6,9)(3,7)(2)(1,8,4)\),設\(q=(5,6,9,3,7,2,1,8,4)\).則這樣的\(p\)到\(q\)的變換構成了一個排列到排列的雙射，
這樣，我們就可以把求\(b\)的值轉化為求\(\{1,2,\cdots,n\}\)中滿足\(q(j)=\min\{q(i)|i\le i \le j \}\)的\(j\)的個數，使得滿足這樣條件的\(j\)的個數為\(k\)的\(n\)元排列數共有\(\left[\begin{array}{c}n\\k\end{array}\right]\)種，（第一類Stirling數）
所以：
\[\overline{b}=\frac{\sum_{i=1}^n\left[\begin{array}{c}n\\i\end{array}\right]\times i}{n!}=H_n=\ln n+O(1) \]
(當\(n\)充分大時，\(O(1)\)的值收斂到歐拉常數)
\[\sigma^2=H_n-H_n^{(2)} \]
其中
\[H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\\H_n^{(2)}=1^2+(\frac{1}{2})^2+(\frac{1}{3})^2+\cdots+(\frac{1}{n})^2 \]
a的平均值分析
\[p=(8,2,7,1,6,9,3,4,5)\\q=(5,6,9,3,7,2,1,8,4)\\ \]
我們定義如下函式
\[y(i,j)=\left\{\begin{array}{l}1,\quad q(i)<q(k),\exist k \in (i,j]\\0,\quad else\end{array}\right. \]
則
\[a=\sum_{1\le i<j\le n}y(i,j) \]
而
\[\overline{y(i,j)}=\frac1{j-i+1}\\\overline a =\sum_{1\leq i<j\leq n}\overline{y(i,j)}=\sum_{1\leq i<j\leq n}\frac1{j-i+1}=\sum_{2\leq r\leq n}\frac{n+1-r}r \]
其中,\(r=j-i+1\)
由上式：
\[\begin{aligned}\overline a&=\sum_{2\leq r\leq n}\frac 1r- \sum_{2\leq r\leq n}1\\&=(n+1)(H_n-1)-(n-1)\\&=(n+1)H_n-2n\\&=n\ln n +O(n)\\&=O(n\log n)+O(n)\end{aligned} \]
\[\sigma^2=2n^2-(n+1)^2H_n^{(2)}-(n+1)H_n+4n \]
由上面計算的\(b\)的均值\(\overline b=\ln n +O(1)=O(\log n)\)
所以演算法的平均時間復雜度是\(O(n\log n)\)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71864.html
標籤：其他
上一篇：netcore專案git忽略提交js,css,ui插件
下一篇：哈希表和碰撞演算法