华东交通大学学报
華東交通大學學報
화동교통대학학보
JOURNAL OF EAST CHINA JIAOTONG UNIVERSITY
2007年
1期
117-119
,共3页
置换%逆序数%轮换
置換%逆序數%輪換
치환%역서수%륜환
令a[1],a[2],…,a[n]是1,2,…,n的一个置换(排列),对任意i,j 比较 a[i],a[j]可计算出置换的逆序数,根据逆序数的奇偶性就得到置换的奇偶性.这要进行n(n-1)/2次比较,时间复杂度是O(n2).本文给出时间复杂度为O(nlog2n)的两种算法:将置换表示为不相交的轮换的积来计算和归并排序的方法来计算.
令a[1],a[2],…,a[n]是1,2,…,n的一箇置換(排列),對任意i,j 比較 a[i],a[j]可計算齣置換的逆序數,根據逆序數的奇偶性就得到置換的奇偶性.這要進行n(n-1)/2次比較,時間複雜度是O(n2).本文給齣時間複雜度為O(nlog2n)的兩種算法:將置換錶示為不相交的輪換的積來計算和歸併排序的方法來計算.
령a[1],a[2],…,a[n]시1,2,…,n적일개치환(배렬),대임의i,j 비교 a[i],a[j]가계산출치환적역서수,근거역서수적기우성취득도치환적기우성.저요진행n(n-1)/2차비교,시간복잡도시O(n2).본문급출시간복잡도위O(nlog2n)적량충산법:장치환표시위불상교적륜환적적래계산화귀병배서적방법래계산.
