Я прохожу старый набор экзаменов для моего курса структур данных и алгоритмов и, похоже, не могу понять, как решить эту проблему.
Вопрос (г) Найдите рекуррентное соотношение для количества умножений, выполненных следующим рекурсивным методом:
static int f(int N)
{
if (N > 1) return 2*f(N - 1);
else return 3;
}
Отвечать:T(N) = T(N − 1) + 1
Я не совсем понимаю, как это отношение находит количество умножений?
T(2) = T(2 - 1) + 1 = 2
T(3) = T(3 - 1) + 1 = 3
Я попытался подключить 2 и 3 к соотношению, но я все еще не понимаю, как это количество умножений. Я на правильном пути?
Для f(N)
у вас есть на один рекурсивный вызов больше, чем для f(N-1)
, поэтому еще одно умножение, таким образом
T(N) = T(N-1) + 1
с базовым случаем T(1) = 0
.