Trovare il caso base per t (n)= t (n - a) + t (a) + cn
-
29-09-2020 - |
Domanda
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.
Soluzione
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