LOG-LOGARITHMIC WORST-CASE RANGE QUERIES ARE POSSIBLE IN SPACE-THETA(N)

被引：189

作者：

WILLARD, DE

机构：

来源：

关键词：

D O I：

10.1016/0020-0190(83)90075-3

中图分类号：

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

学科分类号：

0812 ;

摘要：

引用

页码：81 / 84

页数：4

共 16 条

[1]

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

[2]

Fredman M. L., 1982, 23rd Annual Symposium on Foundations of Computer Science, P165, DOI 10.1109/SFCS.1982.39

[3] ALGORITHMIC AND COMPLEXITY ANALYSIS OF INTERPOLATION SEARCH [J].

GONNET, GH ;

ROGERS, LD ;

GEORGE, JA .

[4]

JOHNSON DB, 1981, CS8113 PENN STAT U R

[5]

Knuth D. E., 1973, ART COMPUTER PROGRAM

[6]

KNUTH DE, 1979, WIDELY DISSEMINATED

[7] INTERPOLATION SEARCH - LOG LOGN SEARCH [J].

PERL, Y ;

ITAI, A ;

AVNI, H .

[8] UNDERSTANDING COMPLEXITY OF INTERPOLATION SEARCH [J].

PERL, Y ;

REINGOLD, EM .

[9]

van Emde Boas P., 1977, INFORMATION PROCESSI, V6, P80

[10]

WILLARD DE, 1982, 20TH ALL C COMM CONT, P462