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

• 作者: 王国胤 胡峰
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 二维表 快速排序 时间复杂度 空间复杂度
• 年，卷（期）: 2007,（6）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 963-968
• 页数: 6页
• 分类号: TP301
• 字数: 4569字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.06.010

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王国胤	重庆邮电大学计算机科学与技术研究所	212	6947	36.0	79.0
5	胡峰	重庆邮电大学计算机科学与技术研究所	10	125	6.0	10.0