《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\rightarrow A\),它的含义是“排列后的数组每个元素从哪里来”。即:变换后,数组下标\(k\)处的数从变换前的下标\(p(k)\)处来。变换后下标为\(p(k)\)处的数从变换前下标为\(p(p(k))\)处的数来……因此我们可以把这条变换的链记为:
\]
每一个下标都在唯一的一个“圈”内(原文这里的用词为"cycle")。举个例子:
对于给定的一个排列:
\]
我们可以观察到这样的规律:
\]
对于括号中的每一行。最后一个等式右侧的数在\(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)的距离之和
*/
最坏情况
最坏的情况如下
\]
此为\(a\)的最坏情况和\(b\)的最好情况。
\]
此为\(a\)的最好情况和\(b\)的最坏情况。
b的平均值分析
对于上面引用的\(p\)的实例:
\]
把所有的圈按照下述规则排列
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数)
所以:
\]
(当\(n\)充分大时,\(O(1)\)的值收敛到欧拉常数)
\]
其中
\]
a的平均值分析
\]
我们定义如下函数
\]
则
\]
而
\]
其中,\(r=j-i+1\)
由上式:
\]
\]
由上面计算的\(b\)的均值\(\overline b=\ln n +O(1)=O(\log n)\)
所以算法的平均时间复杂度是\(O(n\log n)\)
最新文章
- 学习PYTHON之路, DAY 3 - PYTHON 基础 3 (函数)
- iOS - iOS 适配
- CentOS安装Hypernetes相关问题解法
- java多线程之ThreadLocal
- php最简单的文件处理。
- 将meteor部署在自己服务器上的简易方法
- 【PAT】1029. Median (25)
- 使用异步 I/O 大大提高应用程序的性能
- HDFS(Hadoop Distributed File System )
- Perl BEGIN块和END块
- DesignMode的状态处理
- java日期处理函数
- 修改maven本地仓库的默认地址
- 详解Linux chgrp和chown命令的用法
- SQLite Select 语句(http://www.w3cschool.cc/sqlite/sqlite-select.html)
- 【C++】括号匹配
- css3 box-flex
- Python绘制温度变化曲线
- delphi 7里怎么隐藏PageControl控件的tabsheet标签
- C++写文件