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

逆序个数问题算法研究逆序个数问题算法研究 秦韬 全昱立 薛梅 李丽萍 陕西师范大学 计算机科学学院 陕西 西安 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 而最后一种优化是利用分治的方法 通过折中 从而降低复杂度 关键词关键词 逆序数 树状数组 分治归并 算法 Algorithm Research About The Number Of Reverse Problem QIN Tao QUAN Yu li XUE Mei LI Li ping Dept of 2013 School of Computer Science Shaanxi Normal University Xi an 710119 China Abstract 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 through 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 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 Binary 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 KeyKey words words Inverse number Binary Indexed Tree Divide and conquer merge Algorithm 1 1 引言引言 逆序个数问题的描述 逆序个数问题的描述 多人排成一个队列 我们认为从低到高是正确的序列 但是总有部分人不遵守秩序 如果说 前面的人比后面的人高 两人身 高一样认为是合适的 那么我们就认为这两个人是一对 捣乱分子 比如说 现在存在一个序列 176 178 180 170 171 这些捣乱分子对为 那么 现在给出一个整型序列 请找出这些捣乱分子对的个数 仅给出捣乱分子对的数目即可 不用具体的对 输入 为一个文件 in 文件的每一行为一个序列 序列全为数字 数字间用 分隔 输出 为一个文件 out 每行为一个数字 表示捣乱分子的对数 逆序个数问题的原型 逆序数逆序个数问题的原型 逆序数 n 个元素组成的序列 a 1 a 2 a n 若 i j 且 a i a j 则称 a i a j 是一个逆序对 即问题描述的 捣乱分子 对 序列中逆序对的个数称为序列的逆序数 即问题需要求解的捣乱分子的对数 例如 176 178 180 170 171 怎样找逆序数 根据题目意思 对于序列中的每个数字 找出其前面数字中比它大的数字个数 则为它的逆序数对数 序列中所有数字 对应的逆序数对数之和 即为这个序列的总逆序数对数 即有 176 178 180 170 171 0 0 0 3 3 显然 结果应该是 6 那么 根据题目要求 我们便可以设计不同算法进行问题解决 并比较优化得到最佳算法 2 2 算法设计算法设计 2 1 暴力求解算法描述暴力求解算法描述 根据题目的描述与定义 用人类的大脑直接去解 对于序列中的每个数字 找出其前面数字中比它大的数字个数 则为 它的逆序数对数 序列中所有数字对应的逆序数对数之和 即为这个序列的总逆序数对数 这种暴力求解法 对于序列由 10 100或1000个数字组成时的简单逆序数问题还可以 但是随着序列长度的增大 问题的规模变的越来越大 这样的问题就 难以完成 更不用说把问题抽象成循环的机器操作 此问题问题用暴力方法求解 一次递归算法便可得到答案 下面是长度 为n的逆序个数问题可用如下方法实现 分析题意可以得出 当n为1时 逆序对总数为0 当n大于等于2时 移动的过程可分解如下三个步骤 第一步 对于序列中相应位置的每个数 从第二个数开始 比较得出其前面数字中比其大的数的个数 第二步 序列中的总逆序数对数加上正对应比较的数得到的逆序数对数 第三步 进行下一个位置的数字求解对应逆序数对数 其中第一步和第三步是类同的 暴力求解算法如下 算法如下 Main 1 2 freopen test txt r stdin 3 int n total 4 int a 10000 5 cin n 6 for int i 0 i a i 8 total 0 9 for int i 1 i n 1 i 10 for int j 0 j i 1 j 11 if a i a j total 12 cout total endl 暴力求解算法结构清晰 可读性强 而且很容易用数学归纳法证明算法的正确性 然而它的运行效率较低 它的时间复 杂度主要在程序嵌套调用所用的时间 计算逆序数要通过 n n 1 2 此次比较 时间复杂度是 O n2 若在程序中消除暴力 求解涉及的递归调用 使其转化为非递归调用算法 通常 消除递归采用一个用户定义的特殊的数据结构来模拟系统的递归 调用工作 即可采用树状数组优化 2 22 2 树状数组优化算法描述树状数组优化算法描述 树状数组实际上还是一个数组 只不过它的每个元素保存了跟原来数组的一些元素相关的结合值 若A为原数组 定义数 组C为树状数组 C数组中元素C i 表示A i lowbit i 至A i 的结合值 lowbit i 是i的二进制中最后一个不为零的位数 的2次方 可以这样计算lowbit i x 找出最低位的 1 记录最右边的 1 极其右边的数 3 void add int id int pls 41 5 while id maxN 6 7 d id pls 树状数组的 修改 8 id lowbit id 9 10 2 32 3 分治归并排序算法描述分治归并排序算法描述 对序列进行二路归并排序的主要思想是 将序列拆分成若干子序列 先将子序列排序 再合并子序列构成最终排序后的 序列 二路归并算法有一个特点 在进行归并操作时候的两个子序列是有序序列 所以 我们可以利用这一点 在归并子序 列的时候 其中的子序列内部的逆序数必然是0 这时候能产生逆序数的情况必然处于子序列之间 即 位置靠后的子序列 中的元素小于 位置靠前的子序列 的元素 例如 有子序列x 2 4 5 子序列y 1 3 6 显然 子序列y中的元素1的逆序数 为3 子序列y中的元素3的逆序数为2 其他元素的逆序数均为0 通过这样一种方法 我们可以在序列的二路归并排序的过程 中将序列的逆序数计算出来 故其时间复杂度为O nlogn 这里以序列为的例子介绍一种分治归并排序的方法求逆序数 具体步骤如下 Part 1 左边的逆序数 Part 2 右边的逆序数 Part 3 两边有序状态队列的逆序数 Part 1 左边的逆序数 再次递归调用 Part 2 右边的逆序数 再次递归调用 整个算法程序实现如下 整个算法程序实现如下 1 while i mid 4 else 逆序 5 6 number mid i 1 7 a k b j 8 9 3 3 算法分析算法分析 定理定理 1 1 算法 1 是可终止的 证明 定理定理 2 2 算法 1 是有效的 证明 定理定理 3 3 算法 1 的时间复杂度是 O 证明 定理定理 4 4 算法 1 的空间复杂度是 S 证明 1 暴力方法求解 计算逆序数要通过 n n 1 2 此次比较 时间复杂度是 O n2 2 树状数组优化算法 计算逆序数 时间复杂度降为 O nlog2 n 3 分治归并排序算法 计算逆序数 时间复杂度降为 O nlog2 n 4 4 仿真实验与分析仿真实验与分析 本文实验环境 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 5 总总 结结 排序树状数组优化的主要思路是将元素从大到小依次放置在数状数组中 对于每一个元素 i 来说 因它前面的数比它大而 计算出逆序数 t i 利用树状数组的结构特征 即可以 O log2 n 的时间复杂度而统计出 t i 那么 最终总的逆序数为 t i 而最后一种优化是利用