| 置换奇偶性的快速算法 |
| |
| 引用本文： | 周尚超.置换奇偶性的快速算法[J].华东交通大学学报,2007,24(1):117-119. |
| |
| 作者姓名： | 周尚超 |
| |
| 作者单位： | 华东交通大学,江西,南昌,330013 |
| |
| 基金项目： | 江西省自然科学基金
,
国家自然科学基金 |
| |
| 摘 要： | 令a1],a2],…,an]是1,2,…,n的一个置换(排列),对任意i,j比较ai],aj]可计算出置换的逆序数,根据逆序数的奇偶性就得到置换的奇偶性.这要进行n(n-1)/2次比较,时间复杂度是O(n2).本文给出时间复杂度为O(nlog2n)的两种算法:将置换表示为不相交的轮换的积来计算和归并排序的方法来计算.
|
| 关 键 词： | 置换 逆序数 轮换 |
| 文章编号： | 1005-0523（2007）01-0117-03 |
| 收稿时间： | 2006-10-02 |
| 修稿时间： | 2006年10月2日 |
A quick Algorithm for Inversion Number of Permutation |
| |
| ZHOU Shang-chao.A quick Algorithm for Inversion Number of Permutation[J].Journal of East China Jiaotong University,2007,24(1):117-119. |
| |
| Authors: | ZHOU Shang-chao |
| |
| Institution: | East China Jiaotong University, Nanchang 330013 ,China |
| |
| Abstract: | |
| |
| Keywords: | permutation inversion number alternation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《华东交通大学学报》浏览原始摘要信息 |
| 点击此处可从《华东交通大学学报》下载免费的PDF全文 |
|
