Метод распознавания классов алгоритмов на основе асимптотики эластичности функций сложности

Abstract

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

We offer a new indication to recognize the algorithms classes which is based on the asymptotic behavior of the elasticity of complexity functions. The present day analogy for functions of complexity algorithms and produced functions is used, the rate of which is traditionally evaluated by elasticity in econometrics. The theorem that states the characterization of elasticity for rapid, polynomial, subexponential, exponen- tial and hyperexponential algorithms has been proved. The principal advantage of the suggested indication is that it allows the simplicity of computation caused by the well-known properties of elasticity.