《Mathematical Analysis of Algorithms》中有关“就地排列”(In Situ Permutation)的算法分析

问题描述

把数列((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 ightarrow A)，它的含义是“排列后的数组每个元素从哪里来”。即：变换后，数组下标(k)处的数从变换前的下标(p(k))处来。变换后下标为(p(k))处的数从变换前下标为(p(p(k)))处的数来……因此我们可以把这条变换的链记为：

[kleftarrow p(k)leftarrow p(p(k))leftarrow cdots ]

每一个下标都在唯一的一个“圈”内（原文这里的用词为"cycle"）。举个例子：

对于给定的一个排列：

[p=(8,2,7,1,6,9,3,4,5) ]

我们可以观察到这样的规律：

[left{egin{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)=5end{array} ight. ]

对于括号中的每一行。最后一个等式右侧的数在(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)|ile i le j })的(j)的个数。使得满足这样条件的(j)的个数为(k)的(n)元排列数共有(left[egin{array}{c}n\kend{array} ight])种。（第一类Stirling数）

所以：

[overline{b}=frac{sum_{i=1}^nleft[egin{array}{c}n\iend{array} ight] imes 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{egin{array}{l}1,quad q(i)<q(k),exist k in (i,j]\0,quad elseend{array} ight. ]

则

[a=sum_{1le i<jle n}y(i,j) ]

而

[overline{y(i,j)}=frac1{j-i+1}\overline a =sum_{1leq i<jleq n}overline{y(i,j)}=sum_{1leq i<jleq n}frac1{j-i+1}=sum_{2leq rleq n}frac{n+1-r}r ]

其中,(r=j-i+1)

由上式：

[egin{aligned}overline a&=sum_{2leq rleq n}frac 1r- sum_{2leq rleq n}1\&=(n+1)(H_n-1)-(n-1)\&=(n+1)H_n-2n\&=nln n +O(n)\&=O(nlog 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(nlog n))