10.3969/j.issn.1005-0523.2007.01.031
置换奇偶性的快速算法
令a[1],a[2],…,a[n]是1,2,…,n的一个置换(排列),对任意i,j 比较 a[i],a[j]可计算出置换的逆序数,根据逆序数的奇偶性就得到置换的奇偶性.这要进行n(n-1)/2次比较,时间复杂度是O(n2).本文给出时间复杂度为O(nlog2n)的两种算法:将置换表示为不相交的轮换的积来计算和归并排序的方法来计算.
置换、逆序数、轮换
24
O1(数学)
江西省自然科学基金051106;国家自然科学基金10661007
2007-04-29(万方平台首次上网日期,不代表论文的发表时间)
共3页
117-119