Рекуррентное отношение

https://stackoverflow.com/questions/1379929

21-09-2019
|

Вопрос

Почему рекуррентное отношение рекурсивного факторного алгоритма такое?

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

Почему это не так?

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

Ввод значений n, то есть 1,2,3,4......выполняется второе рекуррентное соотношение (факториалы вычислены правильно), а не первое.

Решение

Этот вопрос очень сбивает с толку...Ваша первая формула не является факториальной.Это просто T (n) = n + 1 для всех n.Факториал от n - это произведение первых n натуральных чисел:факториал (1) = 1.факториал (n) = n * факториал (n-1).Ваша вторая формула по существу верна.

Другие советы

Похоже, что T (n) - это рекуррентное отношение временная сложность рекурсивного факторного алгоритма, предполагающего постоянное умножение по времени.Возможно, вы неправильно истолковали свой источник?

обычно мы используем рекуррентное соотношение чтобы найти временную сложность алгоритма.

Здесь функция T (n) на самом деле не предназначена для вычисления значения факториала, но она говорит вам о временной сложности факториального алгоритма.

Это означает, что для нахождения факториала из n потребуется на 1 операцию больше, чем факториал из n-1 (т.е.T(n)=T(n-1)+1) и так далее.

таким образом, правильное рекуррентное соотношение для рекурсивного факториального алгоритма равно T (n) = 1 при n = 0 T (n) = 1 + T (n-1) при n> 0 не то, что вы упомянули позже.

подобное повторение для ханойской башни равно T (n) = 2T (n-1) + 1 при n> 0;

Я предполагаю, что у вас есть неверная информация.Второе рекуррентное соотношение, которое вы приводите является правильный, как вы уже заметили.Первый просто генерирует натуральные числа.

Где вы нашли первый такой ?Это совершенно неправильно.

Он будет добавлять только 1 каждый раз , независимо от значения .

То, что он вложил, было не факториальной рекурсией, а ее временной сложностью.
Предполагая, что это псевдокод для такого повторения:

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)

Я предполагаю, что устранение хвостовой рекурсии не задействовано.

Строки 2 и 3 занимают постоянное время, c1 и c2.
Строка 4 также требует постоянного времени.Однако он вызывает факториал (n-1), который займет некоторое время T (n-1).Кроме того, время, необходимое для умножения факториала (n-1) на n, можно игнорировать, как только используется T (n-1).
Время для всей функции - это просто сумма:T (n) = c1 + c2 + T (n-1).
Это, в обозначении big-o, сводится к T (n) = 1 + T (n-1).

Это, как указал Диам, является плоской рекурсией, поэтому время ее выполнения должно составлять O (n).Однако его пространственная сложность будет огромной.

T (n) = T (n-1) + 1 - правильное рекуррентное уравнение для факториала от n.Это уравнение дает вам время для вычисления факториала от n, а НЕ значения факториала от n.

Сначала вы должны найти базовую операцию, и в данном примере это умножение.Умножение происходит один раз в каждой рекурсии.Итак T (n) = T (n-1) + 1 это + 1 является базовой операцией (многократное повторение для этого примера) T (n-1) - следующий вызов рекурсии.

TL; DR:Ответ на ваш вопрос на самом деле зависит от в какой последовательности ваше рекуррентное отношение является определяющий.То есть, является ли последовательность T_n в вашем вопросе представляет факторная функция или затраты времени выполнения на вычисление факториальной функции^X.

Факторная функция

В рекурсивный определение факториала n, f_n, является:

f_n = n • f_n-1 для n > 0 с f₀ = 1.

Как вы можете видеть, приведенное выше уравнение на самом деле является рекуррентное отношение, поскольку это уравнение это, вместе с начальный срок (т.е., f₀ = 1), рекурсивно определяет последовательность (т.е. факториальная функция, f_n).

Моделирование временных затрат на вычисление факториала

Теперь мы собираемся найти Модель для представления затрат времени выполнения вычисления факториала n.Давайте позвоним T_n в затраты на время выполнения вычислительной техники f_n.

Рассматривая приведенное выше определение факторной функции f_n, стоимость его времени выполнения T_n будет состоять из затрат времени выполнения вычислений f_n-1 (т.е. эта стоимость равна T_n-1) плюс затраты времени выполнения умножения между n и f_n-1.Умножение достигается за постоянное время.Поэтому мы могли бы сказать, что T_n = T_n-1 + 1.

Однако, какова ценность T₀? T₀ представляет собой затраты на вычисление во время выполнения f₀.Поскольку значение f₀ изначально известна по определению стоимость времени выполнения вычислений f₀ на самом деле является постоянным.Следовательно, мы могли бы сказать, что T₀ = 1.

Наконец, то, что мы получаем, это:

T_n = T_n-1 + 1 для n > 0 с T₀ = 1.

Это уравнение, приведенное выше, также является рекуррентное отношение.Однако то, что он определяет (вместе с начальным термином), является последовательностью, которая моделирует затраты времени выполнения вычисления факториальной функции.

^X_{Принимая во внимание, как вызывается последовательность в вашем рекуррентном отношении (т.е., T_n), я думаю, что это, скорее всего, представляет последнее, т. е., затраты времени выполнения на вычисление факториальной функции.}

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow