Encontrar o caso de base para t (n)= t (n - a) + t (a) + cn

Question

Eu estava resolvendo a recorrência usando o método da árvore de recursão: $$ t (n)= t (n - a) + t (a) + cn $$

Quando eu comecei a resolver, eu poderia facilmente concluir o fato de que $ t (a) $ teria computação de custo total na forma de:

$$ h * ca $$ Mas eu não consegui descobrir como resolver o caso da base.

Eu sei que $ t (NA) $ seria na caixa de base quando $ n= A $ .

Mas como calcular a altura $ h $ da recorrência. Eu sei que o caso base pode ser definido como: $$ N-IA= 0 $$

Eu vi os exemplos anteriores no livro introdução aos algoritmos Quais cita:

.

o tamanho subproblema para um nó na profundidade $ i $ é $ n / 4 ^ i $ . Assim, o Tamanho do subproblema hits $ n= 1 $ quando $ n / 4 ^ i= 1 $ ou, equivalentemente, Quando $ i=log_4 n $

Para a recorrência: $ t (n)= 3T (n / 4) + cn ^ 2 $

Então, chegando ao ponto qual seria o caso da base de tal forma que o tamanho do sub-problema atinge $ n= $ como no exemplo acima. .

seria $ n= A $ ?

Por favor, corrija-me se estiver errado. Obrigado.

Answer 1

Cada $ 0 \ le k \ le A $ 9 / span> produz a caixa de base $ t (k) $ . Se você está tentando resolver o BIG-O da recorrência, então você também pode assumir que há alguma $ c $ onde $ T (k) \ le C $ Para cada caso base $ k $ .Isso ajudará a fazer o cálculo um pouco mais fácil