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

《有关“逆序个数问题”的算法设计与分析报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、逆序个数问题算法研究秦韬，全昱立，薛梅，李丽萍(陕西师范大学计算机科学学院，陕西西安710119)摘要：n个元素组成的序列,a[l],a[2],...,a[n]°若i〈j且a[i]>a[j],则称(a[i],a[j])是一个逆序对,或“捣乱分子对”°序列中逆序对的个数称为序列的逆序数。首先，按定义暴力方法求解，计算逆序数要通过n(n・l)/2此次比较，时间复杂度是O(】12)°其次，换一种方法优化，利用树状数组计算逆序数，时间复杂度降为O(nlog2(n))°最后，根据分治归并排序算法计算逆序数，时间复杂度降为O(nlog

2、2(n))。排序树状数组优化的主要思路是将元素从大到小依次放置在数状数组中，对于每一个元素i来说，因它前面的数比它大而计算出逆序数t[i],利用树状数组的结构特征，即可以O(log2(n))的时间复杂度而统计出t[i],那么，最终总的逆序数为》[i]。而最后一种优化是利用分治的方法，通过折中从而降低复杂度。关键词：逆序数；树状数组；分治归并；算法AlgorithmResearchAboutTheNumberOfReverseProblemQINTao,QUANYu-li,XUEMei,LILi-ping(Dept,of20

3、13,SchoolofComputerScience,ShaanxiNonnalUniversity,Xi*an710119,China)Abstract:Sequenceconsistingofnelements,a[1],a[2],…,a[n]・Ifia[j],called(a[i],afjl)isareversepair,or"troublemakerson.uSequenceinreverseorderofthenumbercalledreversenumbersequence.First,by

4、definitionviolentmethodstosolve,countthenuniberofreversethroughn(n-1)/2thecomparison,thetimecomplexityisO(n2).Secondly,foramethodofoptimizingtheuseofcomputingtheinversenumberBinaryIndexedTree,thetimecomplexityisreducedtoO(nlog2(n)).Finally,calculatedaccordingtothe

5、partitionnumberreversemergesortalgorithm,thetimecomplexityisreducedtoO(nlog2(n)).SortBinaryIndexedTreeoptimizationmainideaistobeplacedindecreasingorderofthenumberofelementslikearray,foreachelementi,theresultofitspreviousnumberlargerthanitcalculatedthenumberofrever

6、set[i],theuseofcharacteristicsBinaryIndexedTreestructure,thatcanbeO(log2(n))timecomplexityandthestatisticst[i],thenthefinaltotalnumberofreverse工t[i]・Thefinaloptimizationistheuseofdivideandconquerapproach,throughcompromisetoreducecomplexity.Keywords:Inversenumber;B

7、inaryIndexedTree;Divideandconquermerge;Algorithm1引言逆序个数问题的描述：多人排成一个队列，我们认为从低到高是正确的序列，但是总冇部分人不遵守秩序。如果说，前而的人比后而的人高(两人身高一样认为是合适的)，那么我们就认为这两个人是一对"捣乱分子”，比如说,现在存在一个序列：176,178,180,170,171这些捣乱分子对为<176,170>,<176,171>,<17&170>,<17&171>,<180,170>,<180,171>,那么，现在给出一个整型序列，请找出这

8、些捣乱分子対的个数(仅给出捣乱分子対的数目即可，不用貝体的对)输入：为一个文件(in),文件的毎一行为一个序列。序列全为数字，数字间用”，”分隔。输出：为一个文件(out),每行为一个数字，农示捣乱分子的对数。逆序个数问题的原型：逆序数n个元素组成的序列,a[l],a[2],…,a[n]。若i