摘要
令a[1],a[2],…,a[n]是1,2,…,n的一个置换(排列),对任意i,j比较a[i],a[j]可计算出置换的逆序数,根据逆序数的奇偶性就得到置换的奇偶性.这要进行n(n-1)/2次比较,时间复杂度是O(n2).本文给出时间复杂度为O(nlog2n)的两种算法:将置换表示为不相交的轮换的积来计算和归并排序的方法来计算.
Let ｜a1 ,a2,…,an｜ be a permutation of the set{ 1,2,……n}. If i〈 j and ai 〉 aj then the pair （ai,aj） is called an ＂inversion＂ of the permutation. In this paper, by mergesort method a quick algorithm for inversion number of permutation was gained.
出处
《华东交通大学学报》
2007年第1期117-119,共3页
Journal of East China Jiaotong University
基金
江西省自然科学基金项目(051106)
国家自然科学基金项目(10661007)
关键词
置换
逆序数
轮换
permutation
inversion number
alternation
