- Номер
- Журнал СФУ. Математика и физика. 2009 2 (1)
- Авторы
- Быкова, Валентина В.
- Контактная информация
- Валентина В.Быкова: Институт математики, Сибирский федеральный университет, Свободный 79, Красноярск, 660041 Россия, e-mail:
- Ключевые слова
- сложность вычислений; эластичность алгоритмов; computation complexity; elasticity of algorithms
- Аннотация
Предложен новый признак выявления классов алгоритмов, основанный на асимптотическом поведении эластичности функций сложности. Использована существующая аналогия между функциями сложности алгоритмов и производственными функциями, темп роста которых в эконометрике традиционно оценивается эластичностью. Доказана теорема, устанавливающая характеризацию эластичности для быстрых, полиномиальных, субэкспоненциальных, экспоненциальных и гиперэкспоненциальных алгоритмов. Основное достоинство предложенного признака простота вычисления, обусловленная известными свойствами эластичности.
- Страницы
- 48-62
- Статья в архиве электронных ресурсов СФУ
- https://elib.sfu-kras.ru/handle/2311/884
Журнал СФУ. Математика и физика / Метод распознавания классов алгоритмов на основе асимптотики эластичности функций сложности
Полный текст (.pdf)