Функциональное повторение по константе?

Question

Мне дано это рекуррентное соотношение:

T (n) = T (n − a) + T (a) + cn

C> 0, a> = 1 ..

моя проблема с T (a), я не понимаю, каквы можете "повторить" константу ??

Например, если я пытаюсь построить дерево повторений, я бы сделал следующее:

T (n) =>  cn            =>         cn
         /  \                    /    \
      T(a)  T(n - a)           ca      c*(n-a)
                             /    \     /     \
                            ??    ??  T(n-2a)  T(a)

Вы понимаете, что я имею в виду?Что представляет собой T (a) ??

Любой ресурс будет высоко оценен.Спасибо.

ИЛИ, подумайте об этом итеративно:

T (n) = T (n − a) + T (a) + cn
T (n) = T (n -2a) + T (a) + ????

Answer 1

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

Answer 2

Итак, у вас есть:

T(n) = T(n-a) + T(a) + cn

Что такое T (n-a)? Просто примите n-a в качестве ввода:

T(n-a) = T((n-a)-a) + T(a) + c(n-a)

Теперь, что такое T (a)? Точно так же, принять в качестве ввода:

T(a) = T(a-a) + T(a) + ca

Комбинируя их, вы получаете:

T(n) = ( T((n-a)-a) + T(a) + c(n-a) )+ ( T(a-a) + T(a) + ca ) + cn
     = T(n-2a) + T(a) + c(n-a) + T(0) + T(a) + ca + cn
     = T(n-2a) + 2T(a) + T(0) + c((n-a) + a + n)

Теперь, в зависимости от вашего базового случая, T (0), вероятно, является некоторой константой. Надеюсь, это поможет.