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

摘要：

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].

关键词：树状数组、逆序数、置换、算法、线段树

所属期刊栏目：28

分类号：O241.6;TP301.6(计算数学)

资助基金：国家自然科学基金项目11061014;江西省自然科学基金项目2010GZS0031;华东交通大学科学研究项目091007

在线出版日期：2011-07-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：45-49