《有关“逆序个数问题”的算法设计与分析报告》由会员分享，可在线阅读，更多相关《有关“逆序个数问题”的算法设计与分析报告（7页珍藏版）》请在金锄头文库上搜索。
1、逆序个数问题算法研究秦韬，全昱立，薛梅，李丽萍(陕西师范大学 计算机科学学院，陕西 西安 710119) 摘 要: n 个元素组成的序列，a1,a2,an。若 ij 且 ai aj，则称 （ai,aj）是一个逆序对，或“捣乱分子对”。序列中逆序对的个数称为序列的逆序数。首先，按定义暴力方法求解，计算逆序数要通过 n（n-1）/2 此次比较,时间复杂度是 O（n2）。其次，换一种方法优化，利用树状数组计算逆序数,时间复杂度降为 O（nlog2（n）。最后，根据分治归并排序算法计算逆序数，时间复杂度降为 O（nlog2（n）。排序树状数组优化的主要思路是将元素从大到小依次放置在数状数组中，对于每一
2、个元素 i 来说，因它前面的数比它大而计算出逆序数 ti，利用树状数组的结构特征，即可以O（log2（n）的时间复杂度而统计出 ti，那么，最终总的逆序数为ti。而最后一种优化是利用分治的方法，通过折中从而降低复杂度。关键词: 逆序数; 树状数组；分治归并；算法Algorithm Research About The Number Of Reverse ProblemQIN Tao, QUAN Yu-li , XUE Mei, LI Li-ping(Dept. of 2013, School of Computer Science, Shaanxi Normal University, Xia
3、n 710119, China)Abstract: Sequence consisting of n elements, a 1, a 2, ., a n. If i a j, called (a i, a j) is a reverse pair, or troublemakers on. Sequence in reverse order of the number called reverse number sequence. First, by definition violent methods to solve, count the number of reverse throug
4、h n (n-1) / 2 the comparison, the time complexity is O (n2). Secondly, for a method of optimizing the use of computing the inverse number Binary Indexed Tree, the time complexity is reduced to O (nlog2 (n). Finally, calculated according to the partition number reverse merge sort algorithm, the time
5、complexity is reduced to O (nlog2 (n). Sort Binary Indexed Tree optimization main idea is to be placed in decreasing order of the number of elements like array, for each element i, the result of its previous number larger than it calculated the number of reverse t i, the use of characteristics Binar
6、y Indexed Tree structure, that can be O (log2 (n) time complexity and the statistics t i, then the final total number of reverse t i. The final optimization is the use of divide and conquer approach, through compromise to reduce complexity.Key words: Inverse number; Binary Indexed Tree; Divide and c
7、onquer merge; Algorithm1 引言 逆序个数问题的描述：多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176, 178, 180, 170, 171这些捣乱分子对为, , , , , , 那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)输入:为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。输出：为一个文件(out) ，每行为一个数字，表示捣乱分
8、子的对数。逆序个数问题的原型：逆序数n 个元素组成的序列，a1,a2,an。若 ij 且 aiaj ，则称 （ai,aj）是一个逆序对，即问题描述的“捣乱分子对”。序列中逆序对的个数称为序列的逆序数，即问题需要求解的捣乱分子的对数。例如：176 178 180 170 171怎样找逆序数？根据题目意思，对于序列中的每个数字，找出其前面数字中比它大的数字个数，则为它的逆序数对数，序列中所有数字对应的逆序数对数之和，即为这个序列的总逆序数对数。即有：176 178 180 170 1710 0 0 3 3显然，结果应该是：6。那么，根据题目要求，我们便可以设计不同算法进行问题解决，并比较优化得到最
9、佳算法。2 算法设计2.1 暴力求解算法描述根据题目的描述与定义，用人类的大脑直接去解，对于序列中的每个数字，找出其前面数字中比它大的数字个数，则为它的逆序数对数，序列中所有数字对应的逆序数对数之和，即为这个序列的总逆序数对数。这种暴力求解法，对于序列由10，100或1000个数字组成时的简单逆序数问题还可以，但是随着序列长度的增大，问题的规模变的越来越大。这样的问题就难以完成，更不用说把问题抽象成循环的机器操作。此问题问题用暴力方法求解，一次递归算法便可得到答案。下面是长度为n的逆序个数问题可用如下方法实现。分析题意可以得出，当n为1时，逆序对总数为0，当n大于等于2时， 移动的过程可分解如
10、下三个步骤：第一步 对于序列中相应位置的每个数，从第二个数开始，比较得出其前面数字中比其大的数的个数；第二步 序列中的总逆序数对数加上正对应比较的数得到的逆序数对数；第三步 进行下一个位置的数字求解对应逆序数对数；其中第一步和第三步是类同的。暴力求解算法如下：Main1: 2: freopen(test.txt,r,stdin);3：int n,total;4：int a10000;5：cin n;6：for (int i = 0; i ai;8：total = 0;9：for (int i = 1; i n时，算法结束，否则转第二步；step2: Ci = Ci + x， i = i + l
11、owbit(i)转第一步。i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。求逆序的思路：可以把数一个个插入到树状数组中， 每插入一个数， 统计比他小的数的个数，对应的逆序为 i- getsum( datai )，其中 i 为当前已经插入的数的个数， getsum( datai ）为比 datai 小的数的个数，i- getsum( datai ) 即比 datai 大的个数， 即逆序的个数。最后需要把所有逆序数求和，就是在插入的过程中边插入边求和。具体根据序列为实例描述如下。坐标： 1 2 3 4 5 6 7 8 9d = 0 0 0 0 0 0 0 0 0ans
12、= * * * * * * * * *期中，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 + A
13、14 + A15 + A16树状数组优化算法如下：1: int lowbit(int x)2: return x / 找出最低位的 1， 记录最右边的 1 极其右边的数3: void add(int id,int pls)41: 5: while(id 的例子介绍一种分治归并排序的方法求逆序数，具体步骤如下。Part 1： 左边的逆序数Part 2: 右边的逆序数Part 3： 两边有序状态队列的逆序数 Part 1： 左边的逆序数 再次递归调用Part 2: 右边的逆序数 再次递归调用整个算法程序实现如下：1:while( i = mid & j = End) /两边分别进行比较2: if(
14、bi = bj) /常序3: ak+ = bi+;4: else /逆序5: 6: number += mid - i + 1;7: ak+ = bj+;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（n）。4
15、 仿真实验与分析本文实验环境：CPU，Intel E6320。内存，DDR2；容量，1024MB；硬盘，160GB；缓存，8192KB；，PF使用率：47%-50%集成开发工具：Microsoft Visual C+ 6.0上对逆序个数问题在暴力求解、树状数组和分治归并的执行时间进行仿真。具体实验结果如下：图 2 暴力求解算法运行时间图 3 树状数组算法运行时间图 4 分治归并排序法算法运行时间以下是以上三种算法的对比：表格 1 三种算法的对比算法 运行时间 时间复杂度暴力求解法 0.915 O（n2）树状数组优化法 0.483 O（nlog2（n）分治归并排序法 0.474 O（nlog2（n）而从以上表格，对比可以发现，树状数组优化法和分治归并排序法明显比暴力求解算法运行时间短，时间复杂度也要更低，这与我们预期分析一致。5 总 结排序树状数组优化的主要思路是将元素从大到小依次放置在数状数组中，对于每一个元素 i 来说，因它前面的数比它大而计算出逆序数 ti，利用树状数组的结构特
