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

Полный текст (.pdf)
Номер
Журнал СФУ. Математика и физика. 2011 4 (2)
Авторы
Быкова, Валентина В.
Контактная информация
Быкова, Валентина В. : e-mail:
Ключевые слова
computation complexity; parameterized algorithms; analysis algorithms; elasticity algorithms; сложность вычислений; параметризированные алгоритмы; анализ алгоритмов; эластичность алгоритмов
Аннотация

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

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