2-4 逆序对
设A[1...n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对。
(1)列出数组{2,3,8,6,1}的五个逆序。
(2)如果数组的元素取自{1,2...,n},那么,怎样的数组含有最多的逆序对?
(3)插入排序的时间与输入数组中逆序对的数量之间有怎样的关系?
(4)给出一个算法,能用Θ(n㏒n)的最坏运行时间,确定n个元素的任何排列中你逆序对的数目。(提示:修改合并排序)
解答:
(1) 略
(2)逆序数组
(3)插入排序的时间与输入数组中逆序对的数量呈线性正相关关系。通过观察插入排序的算法伪码可知,算法的运行步骤主要取决于内层循环中元素移动的次数,而每次移动就意味着数组的逆序数减一,当排序结束时逆序数为零。
(4)依据分治法,如果我们将数组分解成两个子序列,分别求出两个子序列的逆序数,再求出两个子序列之间元素的逆序数,就可以得出整个数组的逆序数了。可以做以下考虑:
分解:将问题分成前后两个规模为n/2的数组
解决:分别求解各自的逆序对数。如果子问题规模为2或1,可直接求解。
合并:此时虽然知道两个子序列各自的逆序对数,但两个子序列之间的逆序对数无法轻易获知,如果进行两两比较的话,合并操作的时间复杂度就是n2 ,分治法没有意义。
再考虑上述“合并”的问题,如果此时两个子序列都是有序的话,则通过修改合并排序的MERG过程就可以得出子序列之间的逆序数:在MERG对两个子序列的第一个元素之间进行选则时,如果前一个序列的首元素被选中,则逆序数不变——该元素不会和后一个序列中的剩下元素构成逆序对,如果第二个序列的首元素被选中,则逆序数增加“第一个序列剩下的元素数”——该元素和前一序列中剩下的每个元素构成逆序对,MERG后这些逆序对消除。按着这个思路分治算法重新设计如下:
分解:将问题分成前后两个规模为n/2的数组
解决:分别进行递归合并排序,并记录累加排序所消除的的逆序对数。如果子问题规模为2或1,可直接求解。
合并:通过合并排序的MERG进行合并,在MERG过程中按上述方法累加逆序数。
PS:在最初用分治法考虑问题(4)时,排序的作用在一开并不那么明显,但通过对“合并”的分析,要求对子问题的求解需要产生“排序”的副作用。这种”副作用“在分治法中是值得注意的。
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/longhuihu/archive/2010/07/03/5710589.aspx
分享到:
相关推荐
归并排序求逆序数
利用归并排序求逆序数,复杂度在O(nlgn)含测试用例
利用归并排序实现关于逆序数的计算,Java程序
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
算法导论 课上的 用mergesort求逆序数对的matlab源码,想挣点分,所以就不免费下载了~~~~ 见谅
利用归并排序求逆序对,有分治和递归,不过没有主函数
算法导论课后习题2.3-7合并排序和思考题2-4逆序对答案源码
算法-求排列的逆序数(信息学奥赛一本通-T1237).rar
求逆序数的通用算法.cpp
VC编写的控制台程序,求给定数列的逆序对数,在n*ln(n)时间内完成。
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
逆序数c++源码,直接运行
利用二路归并排序求逆序对,很巧妙的一种算法
算法-求逆序对(信息学奥赛一本通-T1311).rar
求逆序数对1
严蔚敏教材中所讲的将递增的两个顺序表按逆序合并算法的实现。不错的算法,很容易理解。代码可以直接运行
逆序数
采用归并排序的方法来就算一个序列总的逆序数
算法-理论基础- 排序- 逆序对问题(包含源程序).rar
求输入数据后求逆序数问题。常用于本科,研究生的算法作业。里面是工程文件,可以直接使用。