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

Полный текст (.pdf)
Номер
Журнал СФУ. Математика и физика. 2009 2 (1)
Авторы
Быкова, Валентина В.
Контактная информация
Валентина В.Быкова: Институт математики, Сибирский федеральный университет, Свободный 79, Красноярск, 660041 Россия, e-mail:
Ключевые слова
сложность вычислений; эластичность алгоритмов; computation complexity; elasticity of algorithms
Аннотация

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

Страницы
48-62
Статья в архиве электронных ресурсов СФУ
https://elib.sfu-kras.ru/handle/2311/884