The Average Case Analysis of Algorithms : Multivariate Asymptotics and Limit Distributions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

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

Philippe Flajolet
  • Fonction : Auteur
  • PersonId : 829512
Robert Sedgewick
  • Fonction : Auteur

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3162.pdf (3.58 Mo) Télécharger le fichier

Dates et versions

inria-00073527 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073527 , version 1

Citer

Philippe Flajolet, Robert Sedgewick. The Average Case Analysis of Algorithms : Multivariate Asymptotics and Limit Distributions. [Research Report] RR-3162, INRIA. 1997. ⟨inria-00073527⟩
77 Consultations
89 Téléchargements

Partager

Gmail Facebook X LinkedIn More