二维表快速排序的复杂度分析

被引：17

作者：

胡峰

王国胤

机构：

[1] 重庆邮电大学计算机科学与技术研究所

[2] 重庆邮电大学计算机科学与技术研究所重庆西南交通大学信息科学与技术学院成都

来源：

计算机学报 | 2007年 / 06期

关键词：

二维表; 快速排序; 时间复杂度; 空间复杂度;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

在假设二维表数据的排列服从均匀分布的条件下,分析了用快速排序方法对二维表进行排序的过程,给出了整个排序过程的时间复杂度和空间复杂度,得到的平均时间复杂度(O(n×(m+logn)))低于已有文献中对二维表排序的时间复杂度(O(m×n×logn)),其中,m是二维表的关键字个数,n是二维表的记录数.仿真实验说明了文中结论的正确性.这一结果,将有助于进一步设计高效的海量数据分析方法.

引用

页码：963 / 968

页数：6

共 7 条

[1] 一种高效的属性核计算方法 [J].

赵军 ;

王国胤 ;

吴中福 ;

唐宏 ;

李华 ;

廖晓锋 .

小型微型计算机系统, 2003, (11) :1950-1953

[2] 一种新的快速计算正区域的方法 [J].

刘少辉 ;

盛秋戬 ;

史忠植 .

计算机研究与发展, 2003, (05) :637-642

[3] Rough集高效算法的研究 [J].

刘少辉 ;

盛秋戬 ;

吴斌 ;

史忠植 ;

胡斐 .

计算机学报, 2003, (05) :524-529

[4] 粗糙集理论及其应用进展 [J].

胡可云 ;

陆玉昌 ;

石纯一 .

清华大学学报(自然科学版), 2001, (01) :64-68

[5]

算法与数据结构[M]. 电子工业出版社 , 傅清祥, 1998

[6]

计算机算法基础[M]. 华中工学院出版社 , 邹海明, 1985

[7] ROUGH SETS [J].

PAWLAK, Z .

INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES, 1982, 11 (05) :341-356

← 1 →