K-th Number Query问题的改进算法研究

摘要：

K-th number query是计算机算法中的一个基础问题,被广泛作为很多算法实现的重要步骤.对该问题进行了深入研究,并找到了单询问渐近时间复杂度最优的算法.目前一般对于多询问的K-th number query问题使用平衡二叉树解决,询问的时间复杂度为0(lbn).但该算法实现比较复杂,并且常系数较大,提出了基于Bit Indexed Tree数据结构的算法解决,在同等时间复杂度的前提下,实现简单,隐含的常系数很小.最后进行了实验测试,分析显示该新算法不论在时间上还是空间上都优于现有的算法.

关键词： 第K大数查询 位索引树 随机化选择 测试实验 计算机算法

作者: 陈鑫

作者单位: 南京大学,计算机科学与技术系,南京,210093

会议类型: 国内会议

会议名称: 2009年全国理论计算机科学学术年会

会议地点: 哈尔滨

会议语种:中文

页码: 150-152

在线出版日期: 2009-08-07（万方平台首次上网日期，不代表论文的发表时间）