Floors and Ceilings in Divide-and-Conquer Recurrences

被引：0

作者：

Kuszmaul, William ^{[1
]}

Leiserson, Charles E. ^{[1
]}

机构：

[1] MIT CSAIL, Cambridge, MA 02139 USA

来源：

2021 SYMPOSIUM ON SIMPLICITY IN ALGORITHMS, SOSA | 2021年

基金：

美国国家科学基金会;

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The master theorem is a core tool for algorithm analysis. Many applications use the discrete version of the theorem, in which floors and ceilings may appear within the recursion. Several of the known proofs of the discrete master theorem include substantial errors, however, and other known proofs employ sophisticated mathematics. We present an elementary and approachable proof that applies generally to Akra-Bazzi-style recurrences.

引用

页码：133 / 141

页数：9

共 14 条

[1]

Aho Alfred V, 1974, The design and analysis of computer algorithms, P5

[2] On the solution of linear recurrence equations [J].

Akra, M ;

Bazzi, L .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 1998, 10 (02) :195-210

[3]

[Anonymous], 1990, Introduction to Algorithms

[4]

Bentley J. L., 1980, SIGACT News, V12, P36, DOI 10.1145/1008861.1008865

[5]

Campbell Neville, 2020, Recurrences

[6]

Cormen T. H., 2001, The Knuth-Morris-Pratt Algorithm, V2nd

[7]

Cormen TH., 2009, Introduction to Algorithms, V3

[8] A Master Theorem for Discrete Divide and Conquer Recurrences [J].

Drmota, Michael ;

Szpankowski, Wojciech .

JOURNAL OF THE ACM, 2013, 60 (03)

[9]

Leighton Tom, 1996, Notes on better master theorems for divide-and-conquer recurrences

[10] Three Variants of the Master Theorem [J].

Mogos, Andrei-Horia .

19TH INTERNATIONAL CONFERENCE ON CONTROL SYSTEMS AND COMPUTER SCIENCE (CSCS 2013), 2013, :162-166

← 1 2 →