基于树状数组的逆序数计算方法

• 作者: 周娟 曹义亲 谢昕
• 来源期刊: 华东交通大学学报
• 学科: 工学
• 关键词: 树状数组 逆序数 置换 算法 线段树
• 年，卷（期）: 2011,（2）
• 页码范围: 45-49
• 分类号: O241.6|TP301.6
• 字数: 1755字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-0523.2011.02.009

摘要

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)).主要思路是将元素从大到小依次放置在数状数组中,对于每一个元素i来说,因它前面的数比它大而计算出逆序数t[i],利用树状数组的结构特征,即可以O(log2(n))的时间复杂度而统计出t[i],那么最终总的逆序数为∑t[i].

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢昕	华东交通大学信息学院	47	283	8.0	14.0
2	曹义亲	华东交通大学软件学院	47	235	8.0	13.0
3	周娟	华东交通大学软件学院	19	86	6.0	8.0