Je suis bloqué sur une question de récurrence.Récurrence: T (n) = T (n/2) + log N
T (n) = T (n/2) + log N
Ce que j'est en ce moment que:
T (N) = T (N/2) + log N
T (N/2) = T (N/4) + log (N/2)
...
T (N) = T (N/2^k) + somme [i = 0 et k {log (N/2^i)}]
Je suis coincé sur ce qu'il faut faire ensuite. S'il vous plaît donnez-moi quelques suggestions.
Merci!
n'est pas donnée dans l'équation mathématique il est donc préférable si vous résoudre cette question avec l'aide de la version modifiée du théorème de maître. Je fournis ici un lien pour ce genre de problèmes, s'il vous plaît jeter un oeil sur cette question probablement vous obtiendrez ce que vous cherchez. jetez un oeil sur la deuxième réponse s'il vous plaît.
T(1) = c (= c + 0)
T(2) = T(1) + log(2) = c + 1
T(4) = T(2) + log(4) = c + 1 + 2 = c + 3
T(8) = T(4) + log(8) = c + 3 + 3 = c + 6
T(16) = T(8) + log(16) = c + 6 + 4 = c + 10
...
n | T(n) | T(n) - T(n-1)
--+---------------------
1| c + 0| -
2| c + 1| 1
4| c + 3| 2
8| c + 6| 3
16| c + 10| 4
T(n) = c + (log n)(1 + log n)/2 = O(log^2 n)
Une autre façon de voir la même chose:
n = 2^m
S(m) = T(2^m) = T(2^m/2) + log(2^m) = S(m - 1) + m
m | S(m)
--+-----
0 | c
1 | c + 1
2 | c + 1 + 2 = c + 3
3 | c + 3 + 3 = c + 6
4 | c + 6 + 4 = c + 10
...
S(m) = c + m(m + 1)/2
T(2^m) = c + m(m + 1)/2
T(n) = c + (log n)(1 + log n)/2 = O(log^2 n)
Une autre approche consiste à utiliser la Master Theorem (ou sur Wikipedia). Pour la plupart des récurrences, il est applicable et fournit la réponse très rapidement.
Il vous donne essentiellement trois catégories, puis la réponse tombe. Étant donné une récurrence de la forme T (n) = aT (n/b) + f (n), on cherche a, b et f (n). Dans votre cas, nous avons a = 1, b = 2, f (n) = log n.
donc (vous devez regarder les liens référencés) nous tombons dans le cas 2, où f (n) est Theta (n^(log_b (a-EPS)) log^k (n)) = Theta (n^0 log (n)), alors le théorème principal indique que T (n) est en thêta (n^(log_b (a-eps)) log^(k + 1) (n)) = Theta (log^2 (n))
log (N/2^i) = log N - i * log 2 – Nyavro