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

• 作者: 陈鑫
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 第K大数查询 位索引树 随机化选择
• 年，卷（期）: 2009,（21）
• 所属期刊栏目: 理论科学研究
• 页码范围: 150-152
• 页数: 3页
• 分类号: TP311.12
• 字数: 2786字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.21.044

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈鑫	南京大学计算机科学与技术系	27	90	6.0	8.0