文档介绍：binatorics—
A Calculus of Discrete Structures
Philippe Flajolet∗
Abstract In cases (ii) and (iii), a model supposed to reflect the
The efficiency of many discrete algorithms crucially depends distribution of inputs is assumed.
on quantifying properties of large binatorial In the period 1945–1970, both worst-case and
configurations. We survey methods of bina- average-case were considered relevant. For instance, in
torics that are simply based on the idea of associating num- their report to the . Army Ordnance Department
bers to atomic elements binatorial struc- in 1946, Burk, Goldstine, and von Neumann [5] con-
tures, then examining the geometry of the resulting func- duct a thorough discussion of parative merits
tions. In this way, an operational calculus of discrete struc- of binary versus puter arithmetics, proving
tures emerges. Applications to basic algorithms, data struc- in the course of the discussion that “for a sum of bi-
tures, and the theory of random discrete structures are out- nary words, each of length n, the length of the largest
lined. carry sequence is on the average not in excess of log2 n”.
(Their conclusion, based on this and other analyses, is
1 Algorithms and Random Structures worthy of note: “In spite of the long-standing tradition
A prime factor in choosing the best algorithm for a of building digital machines in the decimal system, we
putational task is efficiency with respect to feel strongly in favor of the binary system for our de-
the resources consumed, for instance, auxiliary storage, vice.”)
execution time, amount munication needed. For Knuth in the first three volumes of The Art -
a given algorithm A, such plexity measure being puter Programming (TAOCP) [34] published in the pe-
fixed, what is of interest is the relation riod 1968–1973 brilliantly demonstrated many basic al-
gorithms to be amenable to a thorough mathematical
Size of the problem instance (n)
analysis, leading to a highly valuable classificatio