La résolution de la récurrence T(n) = 2T(sqrt(n))

J'aimerais résoudre la suite de la relation de récurrence:

T(n) = 2T(√n);

Je devine que T(n) = O(log log n), mais je ne suis pas sûr de la façon de le prouver. Comment pourrais-je montrer que cette récurrence résout à O(log log n)?

que serait une "fonction T d'un paramètre appliqué au nombre n". Il n'y a pas de "T de la notation".
Je ne me souviens pas avoir jamais été dans ce fil. Pourquoi avez-vous-moi un message à cette question? Faute par vous?
il y avait une question par vous, ou quelqu'un avec un nom d'utilisateur similaire à la vôtre, poser des questions sur le "T(n) la notation". Il est maintenant supprimé. Une faute de frappe est possible (je n'ai taper le pseudo à la main), mais peu probable, et la façon dont beaucoup de semblables noms d'utilisateur sont là pour commencer?
C'est dans le cache de Google maintenant webcache.googleusercontent.com/search?q=cache:http://... mais je ne sais pas pour combien de temps.
Wow, apparemment le fil est de deux ans. Quelqu'un vient de ressuscité. Si vous avez supprimé le commentaire à l'époque, on pouvait l'oublier; mais alors comment pourrais-je le voir aujourd'hui? C'est un bug dans la matrice...

OriginalL'auteur Tasneem Fathima | 2013-08-07

9

Une idée serait de simplifier la récidive par l'introduction d'une nouvelle variable k tel que 2^k = n. Ensuite, la relation de récurrence pour

T(2^k) = 2T(2^k/2)

Si vous laissez alors S(k) = T(2^k), vous obtenez la récurrence

S(k) = 2(k /2)

Noter que c'est l'équivalent de

S(k) = 2(k /2) + O(1)

Depuis 0 = O(1). Donc, par le Maître Théorème, on obtient que S(k) = Θ(k), puisque nous avons que a = 2, b = 2 et d = 0 et log_b a > d.

Depuis S(k) = Θ(k) et S(k) = T(2^k) = T(n), on obtient que T(n) = Θ(k). Depuis que nous avons pris 2^k = n, ce qui signifie que k = log n, alors T(n) = Θ(log n). Cela signifie que votre supposition initiale de O(log log n) est incorrecte et que l'exécution n'est logarithmique, pas doublement logarithmique. Si il y avait un seul appel récursif être faite, cependant, vous seriez en droit que l'exécution serait de O(log log n).

Espérons que cette aide!

comment se fait-S(k) = T(2^k)? domaine est qui ne coïncident pas, ne devrait-elle pas être S(k') = T(2^k)?
Pouvez-vous élaborer sur ce que tu veux dire sur les domaines qui ne sont pas counciding? Je ne comprends pas ce que vous demandez.
Je voulais dire, comment pouvez-vous remplacer S(k) T(2^k)? Si nous les considérons comme des fonctions de k et 2^k, domaine de T est 1,2,4,8,... Et S est 1,2,3,4,...
Vous avez absolument raison que, en général, vous ne pouvez pas faire des substitutions comme celles-ci. La plupart des récidives vous rencontrez ont la belle propriété qu'ils sont de plus en plus monotone. Si la récidive est monotone croissante et vous pouvez fournir un bond sur sa valeur à différents points de nice (les puissances de deux, les pouvoirs des trois, etc.), ensuite, vous pouvez asymptotiquement lié à l'ensemble de la récidive. C'est ce que nous faisons ici. C'est un truc commun à faire ce que vous n'avez généralement pas voir n'importe qui jamais écrire "c'est monotone" comme une justification, mais il vaut la peine de voir pourquoi ce qui est vrai ici.
Lorsque vous remplacez S(k) T(2^k), pourquoi est-il 2S(k / 2) et pas 2(√k)?

OriginalL'auteur templatetypedef
4

Vous pouvez résoudre ce problème facilement, en déroulant la récursivité:

Maintenant la répétition se termine lorsqu' T(1) = a et vous pouvez trouver les a. Lorsque a = 0 ou 1 il n'a pas de sens mais quand a=2 vous obtiendrez:

La substitution de la k dans la dernière partie de la première équation, vous obtiendrez la complexité de O(log(n)).

Vérifier d'autres semblables récurrences ici:
OriginalL'auteur Salvador Dali

Vous devez vous connecter pour publier un commentaire.