AUTOMATIC AVERAGE-CASE ANALYSIS OF ALGORITHMS
AUTOMATIC AVERAGE-CASE ANALYSIS OF ALGORITHMS
复制标题
DOI：
10.1016/0304-3975(91)90145-r
复制
发表时间：
1991-02-21
影响因子：
1.1
通讯作者：
ZIMMERMANN, P
中科院分区：
文献类型：
--
作者：
FLAJOLET, P;SALVY, B;ZIMMERMANN, P
算法平均案例分析的基本离散组合结构的许多概率特性被证明是可决定的。 本文提出了一个可以开发此类决策程序的一般框架。 它基于用于计数的生成功能技术的组合以及用于渐近估计的复杂分析技术。 。 然后，我们提出相关渐近理论的一些主要组成部分，并表现出可以自动分析的一类天然函数。该理论的公平片段还纳入了一个称为Lambda-upsilon-Omega的系统中。 通过这种方式，使用计算机代数可以自动产生对在各种“可分解”组合结构上运行的算法的非平凡平均案例分析。在基本层面上，本文是全球尝试了解为什么这么多的全球尝试的一部分。基本组合问题倾向于具有基本渐近解决方案。 在某些情况下，事实证明，可以将整个基本组合问题类别相关联，其结构与基本“特殊”功能类别和渐近形式类别相对于计数，概率或平均案例复杂性。
Many probabilistic properties of elementary discrete combinatorial structures of interest for the average-case analysis of algorithms prove to be decidable. This paper presents a general framework in which such decision procedures can be developed. It is based on a combination of generating function techniques for counting, and complex analysis techniques for asymptotic estimations.We expose here the theory of exact analysis in terms of generating functions for four different domains: the iterative/recursive and unlabelled/labelled data type domains. We then present some major components of the associated asymptotic theory and exhibit a class of naturally arising functions that can be automatically analyzed.A fair fragment of this theory is also incorporated into a system called Lambda-Upsilon-Omega. In this way, using computer algebra, one can produce automatically non-trivial average-case analyses of algorithms operating over a variety of "decomposable" combinatorial structures.At a fundamental level, this paper is part of a global attempt at understanding why so many elementary combinatorial problems tend to have elementary asymptotic solutions. In several cases, it proves possible to relate entire classes of elementary combinatorial problems whose structure is well defined with classes of elementary "special" functions and classes of asymptotic forms relative to counting, probabilities, or average-case complexity.