THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE

被引：24

作者：

Chazelle, Bernard ^{[1
]}

Rosenberg, Burton ^{[1
]}

机构：

[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1991年 / 1卷 / 01期

基金：

美国国家科学基金会;

关键词：

Partial-sums; lower-bounds; orthogonal range searching;

D O I：

10.1142/S0218195991000049

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given an array A with n entries in an additive semigroup, and m intervals of the form I-i=[i,j], where 0<i<j <= n, we show that the computation of A[i]+ ... +A[j] for all I-i requires Omega(n+m alpha(m,n)) semigroup additions. Here, a is the functional inverse of Ackermann's function. A matching upper bound has already been demonstrated.

引用

页码：33 / 45

页数：13

共 23 条

[1]

Agarwal P., 1989, J COMBINATORIAL TH A, V52

[2]

ALON N, 1987, 7187 TEL AV U MOIS F

[3] EFFICIENT WORST-CASE DATA-STRUCTURES FOR RANGE SEARCHING [J].

BENTLEY, JL ;

MAURER, HA .

ACTA INFORMATICA, 1980, 13 (02) :155-168

[4] MULTIDIMENSIONAL DIVIDE-AND-CONQUER [J].

BENTLEY, JL .

COMMUNICATIONS OF THE ACM, 1980, 23 (04) :214-229

[5] DECOMPOSABLE SEARCHING PROBLEMS [J].

BENTLEY, JL .

INFORMATION PROCESSING LETTERS, 1979, 8 (05) :244-251

[6] A FUNCTIONAL-APPROACH TO DATA-STRUCTURES AND ITS USE IN MULTIDIMENSIONAL SEARCHING [J].

CHAZELLE, B .

SIAM JOURNAL ON COMPUTING, 1988, 17 (03) :427-462

[7] COMPUTING ON A FREE TREE VIA COMPLEXITY-PRESERVING MAPPINGS [J].

CHAZELLE, B .

ALGORITHMICA, 1987, 2 (03) :337-361

[8] LOWER BOUNDS FOR ORTHOGONAL RANGE SEARCHING .2. THE ARITHMETIC MODEL [J].

CHAZELLE, B .

JOURNAL OF THE ACM, 1990, 37 (03) :439-463

[9] FILTERING SEARCH - A NEW APPROACH TO QUERY-ANSWERING [J].

CHAZELLE, B .

SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :703-724

[10]

Chazelle B., 1989, 5 ANN S COMP GEOM, P131

← 1 2 3 →