Анализ рекурсивных функций

Question

Я пытаюсь проанализировать производительность рекурсивной программы, которую я написал.

Основной код

Cost(x) 
{ 
1 + MIN(Cost(x-1), Cost(x-2), Cost(x-3)) 
} 

Я хочу написать рекуррентное соотношение для числа звонков в стоимость(). Как мне это начать?

Нечто вроде T(x) = T(x/2). Но я не думаю, что это правильно

Редактировать: Я могу представить это как дерево с коэффициентом ветвления 3 для каждого из 3-х рекурсивных вызовов Cost(). Так будет ли это более точно T(x) = T(x/3)?

Answer 1

Количество вызовов, сделанных затрат() будет:

C(x) = 1 + C(x-1) + C(x-2) + C(x-3) 

Таким образом, для ввода x, стоимость() была вызвана один раз плюс количество раз он был вызван на x-1, x-2 и x-3. Это предполагает, что ваше решение не использует memoization. Рекуррентное соотношение не очень: http://www.wolframalpha.com/input/?i=T(x)+%3D+1+%2B+T(x-1)+%2B+T(x-2)+%2B+T(x-3)

Использование запоминания, однако, ваше «число вызовов» становится C(x) = x, потому что вам нужно только оценить C(i) один раз для всех i между 0 и x. (Может быть C(x) = x + 1, в зависимости от ваших начальных условий)

Answer 2

Вы действительно написать рекурсивную решение (я надеюсь, что его присвоение для сравнения с линейной итерации)

я думаю

T(X) = T(X-1)+T(X-2)+T(X-3)+C 
C is small constant