O157 TP31
江西省自然科学基金 , 国家自然科学基金
令a[1],a[2],…,a[n]是1,2,…,n的一个置换(排列),对任意i,j比较a[i],a[j]可计算出置换的逆序数,根据逆序数的奇偶性就得到置换的奇偶性.这要进行n(n-1)/2次比较,时间复杂度是O(n2).本文给出时间复杂度为O(nlog2n)的两种算法:将置换表示为不相交的轮换的积来计算和归并排序的方法来计算.
周尚超.置换奇偶性的快速算法[J].华东交通大学学报,2007,(1):117-119.ZHOU Shang-chao. A quick Algorithm for Inversion Number of Permutation[J]. JOURNAL OF EAST CHINA JIAOTONG UNIVERSTTY,2007,(1):117-119