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

被引：17

作者：

胡峰

王国胤

机构：

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

来源：

计算机学报 | 2007年 / 06期

关键词：

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

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

在假设二维表数据的排列服从均匀分布的条件下,分析了用快速排序方法对二维表进行排序的过程,给出了整个排序过程的时间复杂度和空间复杂度,得到的平均时间复杂度(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
PAWLAK, Z
[J]. INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES, 1982, 11 (05): : 341 - 356

← 1 →