文章基本信息

标题：On Searching Sorted Lists: A Near-Optimal Lower Bound
本地全文：下载
作者：Paul Beame, Faith Fich
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We obtain improved lower bounds for a class of static and dynamic data structure problems that includes several problems of searching sorted lists as special cases. These lower bounds nearly match the upper bounds given by recent striking improvements in searching algorithms given by Fredman and Willard's fusion trees and Andersson's search data structure. Thus they show sharp limitations on the running time improvements obtainable using the unit-cost word-level RAM operations that those algorithms employ.
关键词：Cell-Probe Model, Communication complexity, data structures, lower bounds, Searching