Анализ параметризированных алгоритмов на основе эластичности функций сложности

Abstract

We give a brief overview of results and problems of parameterized algorithmics as the new direction of computational complexity theory. We offer a new indicator of computational complexity for parameterized algorithm which can be used to measure rate a growth of function complexity from many variables. This indicator is a private elasticity of the function complexity. We offer a two-dimensional classification parameterized algorithms to multiplicative forms a presentation of the functions complexity. We give a mathematical basis to analysis a level impact of parameter for time execution of parameterized algorithm

Дан краткий обзор результатов и проблем параметризированной алгоритмики нового направления теории сложности вычислений. Предложен новый показатель вычислительной сложности параметризированного алгоритма, с помощью которого можно измерять темп роста функции сложности многих переменных. Этим показателем является частная эластичность функции сложности. Предложена двумерная классификация параметризированных алгоритмов для мультипликативной формы представления функций сложности. Математически обоснован метод анализа уровня влияния параметра на время работы параметризированного алгоритма.