Trouver le cas de base pour T (n)= T (N - A) + T (a) + CN

Question

Je résolviez la récurrence en utilisant la méthode de l'arborescence de la récursivité: $$ t (n)= t (n - a) + t (a) + cn $$

Quand j'ai commencé à résoudre, je pourrais facilement conclure le fait que $ t (a) $ aurait le calcul total des coûts sous la forme de:

$$ h * CA $$ Mais je ne pouvais pas comprendre comment résoudre le cas de base.

Je sais que $ t $ (na) $ serait au cas de base lorsque $ n= a $ .

Mais comment calculer la hauteur $ H $ de la récurrence. Je sais que le cas de base peut être défini comme suit: $$ n-ia= 0 $$

J'ai vu les exemples précédents dans le livre Introduction aux algorithmes Quelles devis:

la taille du sous-globe pour un nœud à la profondeur $ i $ est $ n / 4 ^ i $ . Ainsi, le Taille de subproblème frappe $ n= 1 $ quand $ n / 4 ^ i= 1 $ ou, de manière équivalente, quand $ i=log_4 n $

Pour la récurrence: $ T (N)= 3T (N / 4) + CN ^ 2 $

Ainsi, en arrivant au point quel serait le cas de base de telle sorte que la taille du sous-problème frappe $ n=? $ dans l'exemple ci-dessus.

serait-ce $ n= a $ ?

S'il vous plaît corrigez-moi si je me trompe. Merci.

Answer 1

Chaque $ 0 \ le k \ le $ donne le cas de base $ t (k) $ . Si vous essayez de résoudre le Big-O de la récurrence, alors vous pouvez aussi supposer que certains $ C $ où $ T (k) \ le c $ pour chaque cas de base $ k $ .Cela aidera à rendre le calcul un peu plus facile