Сложность факториально-рекурсивного алгоритма

Сегодня в классе мой учитель написал на доске этот рекурсивный факториальный алгоритм:

int factorial(int n) {
   if (n == 1) 
       return 1;
   else 
       return n * factorial(n-1);
}

Она сказала, что это имеет стоимость T(n-1) + 1.

Затем с помощью итерационного метода она сказала, что T(n-1) = T(n-2) + 2 = T(n-3) + 3... T(nj) + j, поэтому алгоритм останавливается, когда n - j = 1, поэтому j = n - 1.

После этого она заменила j в T(nj) + j и получила T(1) + n-1.

Она прямо сказала, что для этого n-1 = 2 ^{(log ₂ n-1)} поэтому стоимость алгоритма является экспоненциальной.

Я действительно потерял два последних шага. Может кто-нибудь, пожалуйста, объясните мне их?

Ответ 1

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

T (1) = 1

Для ввода размера n + 1 ваш алгоритм выполняет одну единицу работы внутри самой функции, затем совершает вызов той же функции на входе размера n. Поэтому

T (n + 1) = T (n) + 1

Если вы расширяете условия повторения, вы получаете это

T (1) = 1
T (2) = T (1) + 1 = 2
T (3) = T (2) + 1 = 3
T (4) = T (3) + 1 = 4
...
T (n) = n

Таким образом, в общем случае для этого алгоритма потребуются n единиц работы (т.е. T (n) = n).

Следующее, что сказал ваш учитель, было то, что

T (n) = n = 2 ^{log ₂ n}

Это утверждение верно, потому что 2 ^{log ₂ x}= x для любого ненулевого x, поскольку возведение в степень и логарифмы являются обратными операциями друг друга.

Итак, вопрос: это полиномиальное время или экспоненциальное время? Я бы классифицировал это как псевдополиномиальное время. Если вы обрабатываете вход x как число, то время выполнения действительно является полиномом по x. Тем не менее, полиномиальное время формально определено так, что время выполнения алгоритма должно быть многочленом относительно количества бит, используемых для указания ввода проблемы. Здесь число x может быть указано только в битах & Theta; (log x), поэтому время выполнения 2 ^{log x} технически считается экспоненциальным временем. Я написал об этом как длину в этом более раннем ответе, и я бы рекомендовал посмотреть на него для более подробного объяснения.

Надеюсь, это поможет!