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