Математические методы анализа рекурсивных алгоритмов
View/ Open:
URI (for links/citations):
https://elib.sfu-kras.ru/handle/2311/772Author:
Быкова, Валентина В.
Bykova, Valentina V.
Date:
2008-09Abstract:
Доказана теорема, определяющая асимптотические оценки решения рекуррентного соотношения, характерного для функций временной сложности рекурсивных алгоритмов с аддитивным уменьшением размерности задачи. Представленные результаты вместе с известной основной теоремой о рекуррентных соотношениях дают математический инструмент анализа сложно¬сти двух наиболее типичных принципов организации рекурсии. We prove a theorem that defines asymptotic estimates for the solution of a recurrent relation. This
recurrent relation typically describes time complexity functions for recursive algorithms with an additive
reduction of the dimension of a given problem. The presented results together with a known main theorem
on recurrent relations give a tool for the analysis of the complexity of two most typical recursive schemes.