CLASS OF ALGORITHMS WHICH REQUIRE NON-LINEAR TIME TO MAINTAIN DISJOINT SETS

被引：153

作者：

TARJAN, RE ^{[1
]}

机构：

[1] UNIV BIELEFELD,FAC MATH,D-4800 BIELEFELD,FED REP GER

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1979年 / 18卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0022-0000(79)90042-4

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper describes a machine model intended to be useful in deriving realistic complexity bounds for tasks requiring list processing. As an example of the use of the model, the paper defines a class of algorithms which compute unions of disjoint sets on-line, and proves that any such algorithm requires nonlinear time in the worst case. All set union algorithms known to the author are instances of the model and are thus subject to the derived bound. One of the known algorithms achieves the bound to within a constant factor. © 1979.

引用

页码：110 / 127

页数：18

共 20 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

Borodin A., 1975, COMPUTATIONAL COMPLE

[3]

Doyle J., 1976, Information Processing Letters, V5, P146, DOI 10.1016/0020-0190(76)90061-2

[4]

Fischer M. J., 1972, COMPLEXITY COMPUTER, P153

[5] AN IMPROVED EQUIVALENCE ALGORITHM [J].

GALLER, BA ;

FISHER, MJ .

COMMUNICATIONS OF THE ACM, 1964, 7 (05) :301-303

[6]

Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P294, DOI 10.1137/0202024

[7] INTRINSICALLY EXPONENTIAL COMPLEXITY OF CIRCULARITY PROBLEM FOR ATTRIBUTE GRAMMARS [J].

JAZAYERI, M ;

OGDEN, WF ;

ROUNDS, WC .

COMMUNICATIONS OF THE ACM, 1975, 18 (12) :697-706

[8]

KNUTH DE, 1977, STANCS77599 STANF U

[9]

KNUTH DE, 1975, ART COMPUTER PROGRAM, V3

[10]

Knuth Donald E, 1968, ART COMPUTER PROGRAM, V1

← 1 2 →