Trovare il caso base per t (n)= t (n - a) + t (a) + cn

Question

Stavo risolvendo la recidiva utilizzando il metodo dell'albero di ricorsione: $$ t (n)= t (n - a) + t (a) + cn $$

Quando ho iniziato a risolvere, potrei facilmente concludere il fatto che $ t (A) $ avrebbe un calcolo totale dei costi sotto forma di:

$$ h * c $$ Ma non ho potuto capire come risolvere il caso base.

So che $ t (na) $ sarebbe al caso di base quando $ n= a $ .

Ma come calcolare l'altezza $ h $ della recidiva. So che il caso di base può essere definito come: $$ n-ia= 0 $$

Ho visto i precedenti esempi nel libro Introduzione agli algoritmi Quali citazioni:

.

La dimensione del subproblem per un nodo a profondità $ i $ è $ n / 4 ^ I $ . Quindi, il. Dimensione subproblem hits $ n= 1 $ quando $ n / 4 ^ i= 1 $ o, equivalentemente, Quando $ i=log_4 n $

Per la recidiva: $ t (n)= 3t (N / 4) + cn ^ 2 $

Quindi, venendo al punto quale sarebbe il caso base in modo tale che la dimensione del sub-problema colpisce $ n=? $ come nell'esempio sopra. .

Sarebbe $ N= A $ ?

Per favore correggimi se sbaglio. Grazie.

Answer 1

Ogni $ 0 \ le k \ le a $ produce la custodia di base $ t (k) $ . Se stai cercando di risolvere il Big-O della recidiva, allora potresti anche supporre che ci sia un po 'di class class="container di matematica"> $ c $ dove $ T (k) \ le c $ per ogni caso base $ k $ .Aiuterà a rendere il calcolo un po 'più facile