Как я могу преобразовать функцию входного размера, определенного рекурсивно, в прямую функцию проблемного размера ввода?

Question

Скажем, у меня есть алгоритм, который работает на входе размера n, и я знаю, что время, которое требуется для n, вдвое больше времени, которое требуется для n-1.Я могу наблюдать в этом простом случае (предположим, что для n = 0, скажем, 1 секунда), что алгоритм занимает 2 ⁿ секунд.

Существует ли общий метод преобразования между рекурсивнымиопределений для более знакомого прямого типа выражения?

Answer 1

Основная теорема

В частности:

С T (n) = aT (n / b) + n ^c

Если log _b a c )

Если log _b a = c, то T (n) = O (n ^c log [n])

Если log _b a> c, то T (n) = O (n ^{log _b a} )

Это одна полезная теорема, которую нужно знать, но она не полностью отвечает на ваш вопрос.

То, что вы ищете, является функцией генератора рекуррентного отношения. В общем, они разрешимы только для очень простых случаев, то есть когда f (n) = Af (n-1) + Bf (n-1) и f (0) = f (1) = 1 (или f (1) = А) Другие рекуррентные отношения очень трудно решить.

См. линейное рекуррентное соотношение для получения дополнительной информации.

Answer 2

Такие «рекурсивные функции» называются Отношения рекуррентности , а их «прямые типы» известны как Решение замкнутой формы .

Хотя основная теорема, перечисленная Пойтой, очень полезна для вычисления сложности времени, она не имеет ничего общего с фактическим решением рекуррентных отношений.

Википедия и Математический мир Вольфрама (под "См. Также" ) перечислены замкнутые формы некоторых общих классов рекуррентных отношений. Однако сложные (нелинейные) рекуррентные отношения могут быть очень трудными для поиска решений в замкнутой форме, если они вообще существуют. Не существует общего алгоритма их решения.

Answer 3

Если оно линейное, вы можете выразить отношение в виде матрицы и найти собственные значения, разложив их в форму, которая позволит вам повысить собственные значения до степени, как это было сделано для Фибоначчи