今天学习算法导论第二章中提到的逆序对问题,思前想后采用2种方式比较妥当。具体见下述分析。
逆序对问题:
逆序对(inversion pair)是指在序列{a0,a1,a2...an}中,若ai<aj(i>j),则(ai,aj)上一对逆序对。而逆序数 (inversion number)顾名思义就是序列中逆序对的个数。例如: 1 2 3是顺序,则逆序数是0;1 3 2中(2,3)满足逆序对的条件,所以逆序数只有1; 3 2 1中(1,2)(1,3)(2,3)满足逆序对,所以逆序是3。由定义不难想象,序列n的逆序数范围在[0,n*(n-1)/2],其中顺序时逆序数为 0,对于一个倒序的自然序列{an,an-1,an-2.......3,2,1}来说,是一个完全逆序序列。根据定义我们可以很方便的得到该序列的逆序对总数为 T(N)=∑(i,i<=n)fn,其中fn=(n-1)得到最终结果为T(N)=N*(N-1)/2.
就我所知,目前求这种逆序对最快的算法是利用归并排序,其时间复杂度为O(nlgn), 空间复杂度为O(n)
这里我给出一个O(n*n)的循环算法和一个O(nlgn)的分治算法。
- 循环算法,见下面代码:
public int countByLoop(Integer a[]){
int count=0;
for(int i=0;i<a.length;i++){
for(int j=a.length-1;j>i;j--){
if(a[i]>=a[j]){
count++;
System.out.printf("found=(i=%d,j=%d,a[i]=%d,a[j]=%d)\n",i,j,a[i],a[j]);
}
}
}
return count;
}
2. 分治算法实现如下
public int count(Integer a[],int low,int high){
int count=0;
if(low<high){
int mid=(low+high)/2;
count+=count(a,low,mid); //分治先计算左边的数组
count+=count(a,mid+1,high); //计算右边的数组
count+=mergeCount(a,low,mid,high); //合并两个结算结果
}
return count;
}
/**
* 采用分治法求得逆序对
* @param a
* @return
*/
public int count(Integer a[]){
return count(a,0,a.length-1);
}
private int mergeCount(Integer[] a, int low, int mid, int high) {
int count=0;
int i=low;
int j=mid+1;
while(i<=mid&&j<=high){
if(a[i]<=a[j]){
i++;
}else{
count+=mid-i+1;
for(int k=i;k<=mid;k++){
System.out.printf("(%d,%d)\n",a[k],a[j]);
}
j++;
}
}
while(i<=mid)i++;
while(j<=high)j++;
return count;
}
看到上述的算法,是不是觉得很眼熟呢,不错,其实和我们熟悉的归并排序算法很相似,只是这里不需要额外的辅助内存空间来保存排序
欢迎各位拍砖
分享到:
相关推荐
东莞理工学院--大三--算法分析与设计-实验1-统计逆序对
算法-求逆序对(信息学奥赛一本通-T1311).rar
算法导论课后习题2.3-7合并排序和思考题2-4逆序对答案源码
实验二--单链表逆序排列.pdf
算法-理论基础- 排序- 逆序对问题(包含源程序).rar
算法-数组逆序重存放(信息学奥赛一本通-T1105).rar
[Java算法练习]-数组逆序输出.java
采用启发式模糊匹配算法,对缩略语及候选术语全称从右向左进行逆序扫描,在不要求缩略语中字母全部正确匹配的情况下,识别出规则的术语缩略语及其全称;最后对不规则候选缩略语及全称进行共现分析。同以往算法相比,...
从序和判断的一致性角度定义AHP逆序为:方案合成排序权重比例的改变,方案增减变化时产生逆序是因为这种变化会影响准则权重,相应地,只有对准则的权重进行调整,然后...
算法导论-趣题集锦(1-3):两数之和,霍纳规则,逆序对.
论文研究-AHP逆序研究.pdf, 深刻分析了AHP中逆序产生的原因,指出文献[2]中给出的保序方法的缺陷,提出了新的AHP逆序的解决方案
tableau可视化分析-案例集锦-正序逆序排列
算法-逆序对(洛谷-P1908)(包含源程序).rar
请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。 一个n个元素序列的逆序对个数由三部分构成: (1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分...
统计逆序对 C++ 写的源码 统计一个数组的逆序对
数据结构课程练习---------------------------------------逆序链表的输入输出
基于python实现的逆序算法基于python实现的逆序算法基于python实现的逆序算法基于python实现的逆序算法基于python实现的逆序算法基于python实现的逆序算法基于python实现的逆序算法基于python实现的逆序算法基于...
逆序对,时间复杂度nlogn,采用修改后的合并排序算法
请考虑一个最坏情况O nlogn 的算法确定n个元素的逆序对数目 注意此题请勿用O n^2 的简单枚举去实现 输入格式 第一行:n 表示接下来要输入n个元素 n不超过10000 第二行:n个元素序列 输出格式 逆序对的个数 ...
请考虑一个最坏情况O(nlogn)的算法确定n个元素的逆序对数目。 注意此题请勿用O(n^2)的简单枚举去实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中...