摘要
K-th number query是计算机算法中的一个基础问题,被广泛作为很多算法实现的重要步骤。对该问题进行了深入研究,并找到了单询问渐近时间复杂度最优的算法。目前一般对于多询问的K-th number query问题使用平衡二叉树解决,询问的时间复杂度为O(lbn)。但该算法实现比较复杂,并且常系数较大,提出了基于Bit Indexed Tree数据结构的算法解决,在同等时间复杂度的前提下,实现简单,隐含的常系数很小。最后进行了实验测试,分析显示该新算法不论在时间上还是空间上都优于现有的算法。
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 com plexity 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.
出处
《计算机工程与应用》
CSCD
北大核心
2009年第21期150-152,共3页
Computer Engineering and Applications
