• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Аналитическое решение класса рекуррентных соотношений с аддитивной функцией степенного вида в целях анализа трудоёмкости рекурсивных алгоритмов

Головешкин В., Пономарев А. В., Ульянов М. В.

Предложено аналитическое решение специального класса нелинейных рекуррентных соотношений со степенной аддитивной функцией. Исследуемые рекуррентные соотношения характерны для функций трудоёмкости рекурсивных алгоритмов, разработанных методом декомпозиции и обладающих степенной трудоёмкостью объединения полученных решений. Аналитические решения получены для рекуррентных соотношений с аргументами типа «пол» и «потолок», возникающих при теоретическом рассмотрении исследуемого класса. Результаты позволяют аналитически получить функции трудоёмкости рекурсивных алгоритмов, декомпозирующих решаемую задачу со степенной трудоёмкостью объединения результатов.