有关“逆序个数问题”的算法设计与分析报告

逆序个数问题算法研究秦韬，全昱立，薛梅，李丽萍(陕西师范大学计算机科学学院，陕西西安710119)摘要:n个元素组成的序列，a[1],a[2],…,a[n]。若i〈j且a[i]〉a[j]，则称（a[i],a[j]）是一个逆序对，或“捣乱分子对”。序列中逆序对的个数称为序列的逆序数。首先，按定义暴力方法求解，计算逆序数要通过n（n-1）/2此次比较,时间复杂度是O（n2）。其次，换一种方法优化，利用树状数组计算逆序数,时间复杂度降为O（nlog2（n））。最后，根据分治归并排序算法计算逆序数，时间复杂度降为O（nlog2（n））。排序树状数组优化的主要思路是将元素从大到小依次放置在数状数组中，对于每一个元素i来说，因它前面的数比它大而计算出逆序数t[i]，利用树状数组的结构特征，即可以O（log2（n））的时间复杂度而统计出t[i]，那么，最终总的逆序数为∑t[i]。而最后一种优化是利用分治的方法，通过折中从而降低复杂度。关键词:逆序数;树状数组；分治归并；算法AlgorithmResearchAboutTheNumberOfReverseProblemQINTao,QUANYu-li,XUEMei,LILi-ping(Dept.of2013,SchoolofComputerScience,ShaanxiNormalUniversity,Xi’an710119,China)Abstract:Sequenceconsistingofnelements,a[1],a[2],...,a[n].Ifijanda[i]a[j],called(a[i],a[j])isareversepair,ortroublemakerson.Sequenceinreverseorderofthenumbercalledreversenumbersequence.First,bydefinitionviolentmethodstosolve,countthenumberofreversethroughn(n-1)/2thecomparison,thetimecomplexityisO(n2).Secondly,foramethodofoptimizingtheuseofcomputingtheinversenumberBinaryIndexedTree,thetimecomplexityisreducedtoO(nlog2(n)).Finally,calculatedaccordingtothepartitionnumberreversemergesortalgorithm,thetimecomplexityisreducedtoO(nlog2(n)).SortBinaryIndexedTreeoptimizationmainideaistobeplacedindecreasingorderofthenumberofelementslikearray,foreachelementi,theresultofitspreviousnumberlargerthanitcalculatedthenumberofreverset[i],theuseofcharacteristicsBinaryIndexedTreestructure,thatcanbeO(log2(n))timecomplexityandthestatisticst[i],thenthefinaltotalnumberofreverseΣt[i].Thefinaloptimizationistheuseofdivideandconquerapproach,throughcompromisetoreducecomplexity.Keywords:Inversenumber;BinaryIndexedTree;Divideandconquermerge;Algorithm1引言逆序个数问题的描述：多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176,178,180,170,171这些捣乱分子对为176,170,176,171,178,170,178,171,180,170,180,171,那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)输入:为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。输出：为一个文件(out)，每行为一个数字，表示捣乱分子的对数。逆序个数问题的原型：逆序数n个元素组成的序列，a[1],a[2],…,a[n]。若i〈j且a[i]〉a[j]，则称（a[i],a[j]）是一个逆序对，即问题描述的“捣乱分子对”。序列中逆序对的个数称为序列的逆序数，即问题需要求解的捣乱分子的对数。例如：176178180170171怎样找逆序数？根据题目意思，对于序列中的每个数字，找出其前面数字中比它大的数字个数，则为它的逆序数对数，序列中所有数字对应的逆序数对数之和，即为这个序列的总逆序数对数。即有：17617818017017100033显然，结果应该是：6。那么，根据题目要求，我们便可以设计不同算法进行问题解决，并比较优化得到最佳算法。2算法设计2.1暴力求解算法描述根据题目的描述与定义，用人类的大脑直接去解，对于序列中的每个数字，找出其前面数字中比它大的数字个数，则为它的逆序数对数，序列中所有数字对应的逆序数对数之和，即为这个序列的总逆序数对数。这种暴力求解法，对于序列由10，100或1000个数字组成时的简单逆序数问题还可以，但是随着序列长度的增大，问题的规模变的越来越大。这样的问题就难以完成，更不用说把问题抽象成循环的机器操作。此问题问题用暴力方法求解，一次递归算法便可得到答案。下面是长度为n的逆序个数问题可用如下方法实现。分析题意可以得出，当n为1时，逆序对总数为0，当n大于等于2时，移动的过程可分解如下三个步骤：第一步对于序列中相应位置的每个数，从第二个数开始，比较得出其前面数字中比其大的数的个数；第二步序列中的总逆序数对数加上正对应比较的数得到的逆序数对数；第三步进行下一个位置的数字求解对应逆序数对数；其中第一步和第三步是类同的。暴力求解算法如下：Main1:{2:freopen(test.txt,r,stdin);3：intn,total;4：inta[10000];5：cinn;6：for(inti=0;in;i++)7：cina[i];8：total=0;9：for(inti=1;i=n-1;i++)10：for(intj=0;j=i-1;j++)11：if(a[i]a[j])total++;12：couttotalendl;}暴力求解算法结构清晰，可读性强，而且很容易用数学归纳法证明算法的正确性，然而它的运行效率较低，它的时间复杂度主要在程序嵌套调用所用的时间。计算逆序数要通过n（n-1）/2此次比较,时间复杂度是O（n2）。若在程序中消除暴力求解涉及的递归调用，使其转化为非递归调用算法。通常，消除递归采用一个用户定义的特殊的数据结构来模拟系统的递归调用工作，即可采用树状数组优化。2.2树状数组优化算法描述树状数组实际上还是一个数组，只不过它的每个元素保存了跟原来数组的一些元素相关的结合值。若A为原数组，定义数组C为树状数组。C数组中元素C[i]表示A[i–lowbit(i)+]至A[i]的结合值。lowbit(i)是i的二进制中最后一个不为零的位数的2次方，可以这样计算lowbit(i)=x&(-x)，lowbit(i)=x&(x^(x-1))当想要查询一个sum(n)时，可以依据如下算法即可：step1:令sum=0，转第二步；step2:假如n=0，算法结束，返回sum值，否则sum=sum+Cn，转第三步；step3:令n=n–lowbit(n)，转第二步。n=n–lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。所以修改算法如下（给某个结点i加上x）：step1:当in时，算法结束，否则转第二步；step2:Ci=Ci+x，i=i+lowbit(i)转第一步。i=i+lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。求逆序的思路：可以把数一个个插入到树状数组中，每插入一个数，统计比他小的数的个数，对应的逆序为i-getsum(data[i])，其中i为当前已经插入的数的个数，getsum(data[i]）为比data[i]小的数的个数，i-getsum(data[i])即比data[i]大的个数，即逆序的个数。最后需要把所有逆序数求和，就是在插入的过程中边插入边求和。具体根据序列为123456789实例描述如下。坐标：123456789d[]=000000000ans[]=*********期中，d数组是树状数组，ans数组为每一位逆序数的值。拓展建立树形图如下。图1树状数组令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：C1=A1C2=A1+A2C3=A3C4=A1+A2+A3+A4C5=A5C6=A5+A6C7=A7C8=A1+A2+A3+A4+A5+A6+A7+A8...C16=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12+A13+A14+A15+A16树状数组优化算法如下：1:intlowbit(intx)2:{returnx&(-x);}//找出最低位的1，记录最右边的1极其右边的数3:voidadd(intid,intpls)41:{5:while(id=maxN)6:{7:d[id]+=pls;//树状数组的修改8:id+=lowbit(id);9:}10:}2.3分治归并排序算法描述对序列进行二路归并排序的主要思想是：将序列拆分成若干子序列，先将子序列排序，再合并子序列构成最终排序后的序列。二路归并算法有一个特点，在进行归并操作时候的两个子序列是有序序列，所以，我们可以利用这一点，在归并子序列的时候，其中的子序列内部的逆序数必然是0，这时候能产生逆序数的情况必然处于子序列之间，即：“位置靠后的子序列”中的元素小于“位置靠前的子序列”的元素。例如，有子序列x：2,4,5；子序列y:1,3,6，显然，子序列y中的元素1的逆序数为3,子序列y中的元素3的逆序数为2，其他元素的逆序数均为0。通过这样一种方法，我们可以在序列的二路归并排序的过程中将序列的逆序数计算出来。故其时间复杂度为O(nlogn)。这里以序列为53681732028的例子介绍一种分治归并排序的方法求逆序数，具体步骤如下。Part1：左边的逆序数Part2:右边的逆序数Part3：两边有序状态队列的逆序数Part1：左边的逆序数再次递归调用Part2:右边的逆序数再次递归调用整个算法程序实现如下：1:while(i=mid&&j=End)//两边分别进行比较2:{if(b[i]=b[j])//常序3:a[k++]=b[i++];4:else//逆序5:{6:number+=mid-i+1;7:a[k++]=b[j++];8:}9:}3算法分析定理1.算法1是可终止的。证明：…..定理2.算法1是有效的。证明：…..定理3.算法1的时间复杂度是O()。证明：…..定理4.算法1的空间复杂度是S()。证明：…..1)暴力方法求解，计算逆序数要通过n（n-1）/2此次比较,时间复杂度是O（n2）。2)树状数组优化算法，计算逆序数,时间复杂度降为O（nlog2（n））。3)分治归并排序算法，计算逆序数，时间复杂度降为O（nlog2（