返回Google圖書搜尋

Two Algorithms for Searching in a K-key Table

Xiaojun ShenUniversity of Illinois at Urbana-Champaign. Department of Computer ScienceH. Edelsbrunner

出版	Department of Computer Science, University of Illinois at Urbana-Champaign, 1990
URL	http://books.google.com.hk/books?id=N49BONtO_KIC&hl=&source=gbs_api

註釋Abstract: "This paper considers a multikey search problem for implicit data structures. More specifically, n k-key items (k a constant) are to be stored in a k-by-n array (one item per column) so that given a key the corresponding item can be found efficiently. We present two algorithms for this problem. One takes O(log n) time, which matches the complexity of the previous optimal but more complicated algorithm of Fiat et al. The other algorithm takes time O(log℗n) for a search, but the multiplicative constant is smaller so that its performance is better than that of the O(log n) algorithms as long as n is not unreasonably large."