The Average Case Analysis of Algorithms : Multivariate Asymptotics and Limit Distributions

Philippe Flajolet 1 Robert Sedgewick
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This report is part of a series whose aim is to present in a synthetic way the major methods of «analytic combinatorics» needed in the average--case analysis of algorithms. It develops a general approach to the distributional analysis of parameters of elementary combinatorial structures like strings, trees, graphs, permutations, and so on. The methods are essentially analytic and relie on multivariate generating functions, singularity analysis, and continuity theorems. The limit laws that are derived mostly belong to the Gaussian, Poisson, or geometric type.
Type de document :
Rapport
[Research Report] RR-3162, INRIA. 1997
Liste complète des métadonnées

https://hal.inria.fr/inria-00073527
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:07:29
Dernière modification le : samedi 17 septembre 2016 - 01:27:28
Document(s) archivé(s) le : lundi 17 septembre 2012 - 14:40:35

Fichiers

Identifiants

  • HAL Id : inria-00073527, version 1

Collections

Citation

Philippe Flajolet, Robert Sedgewick. The Average Case Analysis of Algorithms : Multivariate Asymptotics and Limit Distributions. [Research Report] RR-3162, INRIA. 1997. 〈inria-00073527〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

98