SURPASSING THE INFORMATION-THEORETIC BOUND WITH FUSION TREES

被引：209

作者：

FREDMAN, ML

WILLARD, DE

机构：

[1] UNIV CALIF SAN DIEGO,LA JOLLA,CA 92093

[2] SUNY ALBANY,ALBANY,NY 12222

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1993年 / 47卷 / 03期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0022-0000(93)90040-4

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper introduces a new sublogarithmic data structure for searching, the fusion tree. These trees lead to improved worst-case algorithms for sorting and searching, surpassing the limitations of the information theoretic lower bound. © 1993.

引用

页码：424 / 436

页数：13

共 7 条

[1] HASH FUNCTIONS FOR PRIORITY-QUEUES [J].

AJTAI, M ;

FREDMAN, M ;

KOMLOS, J .

INFORMATION AND CONTROL, 1984, 63 (03) :217-225

[2]

[Anonymous], 1972, ACTA INFORM, DOI [10.1007/BF00288683, DOI 10.1007/BF00288683]

[3]

BOAS PV, 1977, MATH SYST THEORY, V10, P99

[4]

Dietzfelbinger M., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P524, DOI 10.1109/SFCS.1988.21968

[5]

PAUL W, 1984, 1980 S LOG ALG ZUR 1, P85

[6]

WILLARD D, 1983, INFORM PROCESS LETT, P81

[7] NEW TRIE DATA-STRUCTURES WHICH SUPPORT VERY FAST SEARCH OPERATIONS [J].

WILLARD, DE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 28 (03) :379-394

← 1 →