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

Question

я даюсь это рекуррентное соотношение:

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

C> 0, а> = 1 ..

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

Мол, если я пытаюсь построить рекуррентное дерево, я бы, делая это:

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

Так у вас есть:

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

Что такое Т (п-а)? Просто возьмите 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), вероятно, является некоторая постоянная. Надеюсь, что помогает.

Answer 2

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