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

Algorithm of Inverse Number Based on Arborescence Array

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

Suppose there is a permutation of a[1],a[2],…,a[n] that is constituted by n elements.If ij and a [i]a [j],then（a[i],a[j]） is called an inverted sequence pair.The number of inverted sequence in a permutation is called inverse number of a permutation.According to the definition,the caculation of inverse number must be compared with n（n-1）/2,and the time complexity is O（n2）.A new method is devised to calculate the reverse numble by arborescence array and reduce the time complexity to O（nlog2（n））.The principal idea of this method is to place elements into arborescence array in descending order.With regard to each element,since the previ-ous number which is bigger and being worked out at reverse number t[i],when taking advantage of the architec-tural feature of arborescence array,it will come to t[i] by the time complexity of O（log2（n）） and finally reach the total reverse number as ∑t[i].