置换奇偶性的快速算法

• 作者: 周尚超
• 来源期刊: 华东交通大学学报
• 学科: 数学
• 关键词: 置换 逆序数 轮换
• 年，卷（期）: 2007,（1）
• 所属期刊栏目: 基础科学
• 页码范围: 117-119
• 页数: 3页
• 分类号: O1
• 字数: 1423字
• 语种: 中文
• DOI: 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)的两种算法:将置换表示为不相交的轮换的积来计算和归并排序的方法来计算.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周尚超		29	111	5.0	10.0