Exact Asymptotics of Divide-and-Conquer Recurrences

作者: Philippe Flajolet , Mordecai Golin

DOI: 10.1007/3-540-56939-1_68

关键词:

摘要: The divide-and-conquer principle is a major paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in algorithm. This work shows periodicity phenomena, often fractal nature, are ubiquitous performances these algorithms. Mellin transforms and Dirichlet series to attain precise asymptotic estimates. method illustrated by detailed average case, variance distribution analysis classic top-down recursive mergesort

参考文章(18)
L. Devroye, Moment Inequalities for Random Variables in Computational Geometry Computing. ,vol. 30, pp. 111- 119 ,(1983) , 10.1007/BF02280782
Philippe Dumas, Récurrences mahlériennes, suites automatiques, études asymptotiques Université Sciences et Technologies - Bordeaux I. ,(1993)
Donald Ervin Knuth, Sorting and Searching ,(1973)
Christian Buchta, On the average number of maxima in a set of vectors Information Processing Letters. ,vol. 33, pp. 63- 65 ,(1989) , 10.1016/0020-0190(89)90156-7
Kenneth B. Stolarsky, Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity SIAM Journal on Applied Mathematics. ,vol. 32, pp. 717- 730 ,(1977) , 10.1137/0132060
Jean-Marie Dumont, Alain Thomas, Systems of numeration and fractal functions relating to substitutions (French) Theoretical Computer Science. ,vol. 65, pp. 153- 169 ,(1989) , 10.1016/0304-3975(89)90041-8
Jon Louis Bentley, Hsiang-Tsung Kung, Mario Schkolnick, Clark D Thompson, On the Average Number of Maxima in a Set of Vectors and Applications Journal of the ACM. ,vol. 25, pp. 536- 543 ,(1978) , 10.1145/322092.322095
Jean-Paul Allouche, Henri Cohen, Dirichlet Series and Curious infinite Products Bulletin of the London Mathematical Society. ,vol. 17, pp. 531- 538 ,(1985) , 10.1112/BLMS/17.6.531