Quelqu'un peut-il aider à résoudre cette relation de récurrence? [fermé]

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

Dans la première j'utilise la méthode de substitution pour n, logn, etc; tout m'a donné des réponses erronées.
arbres Récurrence. Je ne sais pas si je peux appliquer la racine sera une constante

Quelqu'un peut-on aider?

Answer 1

regard Let au premier. Tout d'abord, vous devez savoir T (cas de base). Vous avez dit que c'est une constante, mais quand vous le problème, il est important que vous écrivez. Habituellement, il est quelque chose comme T (1) = 1. Je vais utiliser, mais vous pouvez généraliser à quoi que ce soit.

Ensuite, savoir combien de fois vous réapparaissent (qui est, la hauteur de l'arbre de récursivité). n est la taille de votre problème, alors combien de fois peut-on diviser à plusieurs reprises par 2 n? Mathématiquement parlant, ce que j'est quand n/(2^i) = 1? Figure dehors, prise sur elle pour plus tard.

Ensuite, faire quelques substitutions, jusqu'à ce que vous commencez à remarquer un motif.

T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)

Ok, la tendance est que l'on multiplie T () 2 par un certain nombre de fois, et diviser par 2 n un certain nombre de fois. Combien de fois? temps de i.

T(n) = (2^i)*T(n/(2^i)) + ...

Pour les termes de grands-? à la fin, nous utilisons un truc mignon. Regardez au-dessus où nous avons quelques substitutions, et ignorer la partie T (). Nous voulons que la somme des termes de thetav. Notez que ils ajoutent à (1 + 2 + 4 + ... + 2^i) * θ(1). Pouvez-vous trouver une forme fermée pour 1 + 2 + 4 + ... + 2^i? Je vais vous donner que l'un; il est (2^i - 1). Il est un bon à mémoriser juste, mais voici comment vous figurez dehors .

Quoi qu'il en soit, dans l'ensemble, nous obtenons

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)

Si vous avez résolu pour i plus tôt, alors vous savez que i = log_2(n). Branchez que, faire un peu d'algèbre, et vous obtenez jusqu'à

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. Alors T(n) = n + (n - 1)*θ(1). N fois une constante, plus une constante, plus n. Nous laissons tomber plus bas termes et des constantes d'ordre, il est donc ? (n).

Prasoon Saurav est juste sur l'utilisation de la méthode maître, mais il est important que vous savez ce que dit la relation de récurrence. Les choses à demander, comment beaucoup de travail que je fais à chaque étape, et quel est le nombre d'étapes pour une entrée de la taille n?

Answer 2

Master Theorem pour résoudre de telles relations de récurrence.

  

Soit a est un nombre entier supérieur à ou égal à 1 et b être un nombre réel supérieur à   1. Soit c un nombre réel positif et    d un réel positif. Compte tenu de la récurrence de la forme

     

  

• T (n) = a T (n / b) + n ^c .. si n> 1

  

• T (n) = d .. si n = 1

  

     

n alors pour une puissance de b,

     

  
1. si log _b a c )
  
2. si log _b a = c, T (n) = T (n ^c log n),
  
3. si log _b a> c, T (n) = T (n ^{log _b a} ).
  

1) T(n) = 2T(n/2) + 0(1)

Dans ce cas,

a = b = 2;
   log _b a = 1; c = 0 (à partir du n ^c = 1 => c = 0)

Cas (3) est applicable. Alors T(n) = Θ(n):)

---

2) T(n) = T(sqrt(n)) + 0(1)

Soit m = log ₂ n;

=> T (2 ^m ) = T (2 ^{m / 2} ) + 0(1)

Maintenant renommer K (m) = T (2 ^m ) => K (m) = K (m / 2) + 0(1)

Appliquer cas (2).

---

Answer 3

Pour la partie 1, vous pouvez utiliser le théorème maître comme le suggère @Prasoon Saurav.

Pour la partie 2, développez simplement la récurrence:

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

La série continuera à des conditions de k jusqu'à n ^ 1/(2^k) <= 1, à savoir 2^k = log n ou k = log log n. Cela donne T(n) = k * O(1) = O(log log n).

Answer 4

regard Let à la première récidive, T (n) = 2T (n / 2) + 1. Le n / 2 est notre indice ici: paramètre de chaque terme emboîté est la moitié de celle de son parent. Par conséquent, si nous commençons par n = 2 ^ k alors nous aurons k termes dans notre expansion, chacun ajoutant 1 au total, avant d'atteindre notre scénario de base, T (0). Par conséquent, en supposant T (0) = 1, on peut dire T (2 ^ k) = k + 1. Maintenant, puisque n = 2 ^ k nous devons avoir k = log_2 (n). Par conséquent, T (n) = log_2 (n) + 1.

On peut appliquer la même astuce à votre deuxième récurrence, T (n) = T (n ^ 0,5) + 1. Si on commence avec n = 2 ^ 2 ^ k nous aurons k termes dans notre expansion, chacun ajoutant 1 au total. En supposant T (0) = 1, il faut avoir T (2 ^ 2 ^ k) = k + 1. Puisque n = 2 ^ 2 ^ k nous devons avoir k = log_2 (log_2 (n)), d'où T (n) = log_2 (log_2 (n)) + 1.

Answer 5

relations de récurrence et fonctions récursives ainsi devrait être résolu en commençant par f (1). Dans le cas 1, T (1) = 1; T (2) = 3; T (4) = 7; T (8) = 15; Il est clair que T (n) = 2 * n-1, qui, dans la notation O est O (n).
En second cas, T (1) = 1; T (2) = 2; T (4) = 3; T (16) = 4; T (256) = 5; T (256 * 256) = 6; Il faudra peu de temps pour savoir que T (n) = log (log (n)) + 1 où log est dans la base 2. Il est clair que cela est O (log (log (n)) relation.

Answer 6

La plupart du temps la meilleure façon de faire face à la récurrence est d'attirer l'arbre de récurrence et soigneusement traiter le cas de base.

Mais ici, je vais vous donner une légère allusion à résoudre en utilisant la méthode de substitution.

Dans la récurrence première n = 2^k de substitution try Dans la récurrence seconde substitution essayer n = 2^2^k