计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (21): 150-152.DOI: 10.3778/j.issn.1002-8331.2009.21.044

• 理论科学研究 • 上一篇    下一篇

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

陈 鑫   

  1. 南京大学 计算机科学与技术系,南京 210093
  • 收稿日期:2009-05-04 修回日期:2009-06-09 出版日期:2009-07-21 发布日期:2009-07-21
  • 通讯作者: 陈 鑫

Improvement of K-th number query problem algorithm

CHEN Xin   

  1. Department of Computer Science and Technology,Nanjing University,Nanjing 210093,China
  • Received:2009-05-04 Revised:2009-06-09 Online:2009-07-21 Published:2009-07-21
  • Contact: CHEN Xin

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

Abstract:

The K-th number query is a fundamental problem in computer algorithm,which is a subroutine of numerous problems.Researchers have done a lot of further work including the linear time algorithm for single K-th number query.The time complexity O(lb n) for each query solution has already been found for the multi-queries K-th number query problem,with the help of balance search tree structure.But the BST-based algorithm is not very easy to implement as well as a big constant factor hidden in the Big-O representation.This paper introduces an algorithm based on Bit Indexed Tree to tackle K-th number query with easy implementation and small constant factor.Finally,the experiment shows that the new algorithm is remarkably faster than previous algorithms with nearly optimal memory usage.