BOUNDED ORDERED DICTIONARIES IN O(LOG LOG N) TIME AND O(N) SPACE

被引：39

作者：

MEHLHORN, K

NAHER, S

机构：

[1] Fachbereich 14, Universität des Saarlandes

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 35卷 / 04期

关键词：

computational complexity; Data structures; dictionary; hashing; search tree;

D O I：

10.1016/0020-0190(90)90022-P

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we show how to implement bounded ordered dictionaries, also called bounded priority queues, in O(log log N) time per operation and O(n) space. Here n denotes the number of elements stored in the dictionary and N denotes the size of the universe. Previously, this time bound required O(N) space. © 1990.

引用

页码：183 / 189

页数：7

共 11 条

[1] BOAS PV, 1974, 74 CORN U DEP COMP S
[2] BOAS PV, 1977, MATH SYST THEORY, V10, P99
[3] DIETZFELBINGER M, 1988, 29TH P IEEE S F COMP
[4] STORING A SPARSE TABLE WITH O(1) WORST CASE ACCESS TIME
FREDMAN, ML
KOMLOS, J
SZEMEREDI, E
[J]. JOURNAL OF THE ACM, 1984, 31 (03) : 538 - 544
[5] JOHNSON DB, 1982, MATH SYST THEORY, V15, P295
[6] KARLSSON RG, 1984, CS8450 U WAT DEP COM
[7] Mehlhorn K., 1984, DATA STRUCTURES ALGO
[8] MEHLHORN K, 1989, P MFCS 89, P88
[9] van Emde Boas P., 1977, INFORMATION PROCESSI, V6, P80
[10] WILLARD D, 1984, J COMPUT SYST SCI, V28, P395

← 1 2 →