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

n个元素组成的置换a1],a2],…,an].若i＜j且ai]＞aj],则称(ai],aj])是一个逆序对.置换中逆序对的个数称为置换的逆序数.按定义,计算逆序数要通过n(n-1)/2此次比较,时间复杂度是O(n2).设计了一种新的方法,利用树状数组计算逆序数,时间复杂度降为O(nlog2(n)).主要思...

Algorithm of Inverse Number Based on Arborescence Array

Suppose there is a permutation of a1],a2],…,an] that is constituted by n elements.If ij and a i]a j],then（ai],aj]） 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 ti],when taking advantage of the architec-tural feature of arborescence array,it will come to ti] by the time complexity of O（log2（n）） and finally reach the total reverse number as ∑ti].