文章基本信息

标题：Tables should be sorted (on random access machines)
本地全文：下载
作者：Faith Fich ; Peter Bro Miltersen
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1995
卷号：2
期号：26
出版社：Aarhus University
摘要：We consider the problem of storing an n element subset S of a universe of size m, so that membership queries (is x in S?) can be answered efficiently. The model of computation is a random access machine with the standard instruction set (direct and indirect addressing, conditional branching, addition, subtraction, and multiplication). We show that if s memory registers are used to store S, where n time Omega(log n) is necessary in the worst case. That is, under these conditions, the solution consisting of storing S as a sorted table and doing binary search is optimal. The condition s we show that if n + m/n^o(1) registers may be used, query time o(log n) is possible.