Résoudre une relation de récurrence avec T (N)= 2 * T (n / 3) + 5N [duplicate]

Question

Cette question a déjà des réponses ici :

Résolution des relations de récurrence pour les séquences de chiffres (11 réponses)

fermé Il y a 8 mois .

Je n'ai aucune idée de la façon de résoudre celui-ci - je finis avec $ \ sum_ {i= 0} ^ k (2 ^ k * 5 * 3 ^ i) $ < / SPAN> Mais je n'ai aucune idée de savoir comment obtenir plus loin que cela (par exemple, résoudre la somme encore plus loin, si elle est même correcte de commencer).

Ceci est le théorème de la tâche - Masters n'est pas autorisé:

t (n)= 2 * t (n / 3) + 5n

t (1)= 5

Et nous savons que n= 3 ^ k

Merci pour tous vos conseils et votre aide!

Answer 1

Nous pouvons utiliser la méthode de la maîtrise pour résoudre ce problème.

a = 2
b = 3
n^(log(a)base(b)) = n^(log(2)base(3)) = n^(0.63)
Now, f(n) = 5n
f(n) > n^(0.63)
so,
if time complexity = T(n), then using master's theorem:
T(n) = Theta(5n) = Theta(n)

---

Sans utilisation du théorème de maître: utilisation de la méthode de substitution

T(n) = 2 * T(n/3) + 5n
     = 2 * [2 * T(n/(3^2)) + 5(n/3)] + 5n
       simplifying:
     = (2^2) * T(n/(3^2)) + (2/3)5n + 5n
     ...
     = (2^k) * T(n/(3^k)) + [(2/3)^(k-1)]*5n + ... + (2/3)^0 * 5n -----(1)
     The value of k:
         n/(3^k) = 1
         k = log(n) base 3 ----- (2)
     using (2) in (1)
     = (2^k) * 5 + [(2/3)^(k-1)]*5n + ... + (2/3)^0 * 5n
     = 5 * [(2^k) + [(2/3)^(k-1)] * n + ... + (2/3)^0 * n] ------ (3)
     = 2^k = 2^(log n base 3) = n ^ (log 2 base 3) = n ^ 0.63 -------(4)
     substituting (4) into (3)
     = 5 * [(n^0.63) + n * {(2/3)^(k-1) + .... (2/3)^0}]
     The term in {curly brace} is a GP, after solving it is O(1)
     = 5 * [(n^0.63) + n*O(1)]
    n * O(1) + (n ^ 0.63) = n
     = 5 * n
Hence complexity, T(n) = O(n)