La résolution de la relation de récurrence T(n) = √n T(√n) + n
Est-il possible de résoudre la relation de récurrence
T(n) = √n T(√n) + n
L'aide du Maître Théorème? Il n'est pas de la forme
T(n) = a ⋅ T(n /b) + f(n)
mais ce problème est donnée dans l'exercice des PLC chapitre 4.
Une question similaire: math.stackexchange.com/questions/689887/...
OriginalL'auteur ahollyhock | 2011-09-02
Vous devez vous connecter pour publier un commentaire.
Cela ne peut pas être résolu par le Maître Théorème. Cependant, il peut être résolu en utilisant la récursivité de la méthode d'arbre à résoudre à O(n log log n).
L'intuition derrière cela est d'avis que, à chaque niveau de l'arbre, vous êtes en train de faire n de travail. Le haut niveau ne n travail de manière explicite. Chaque √n sous-problèmes ne √n des travaux pour un montant total net de n de travail, etc. Donc la question est maintenant de savoir à quelle profondeur la récursivité est un arbre. Eh bien, c'est le nombre de fois que vous pouvez prendre la racine carrée de n avant n devient suffisamment petit (disons, moins de 2). Si nous écrire
puis sur chaque appel récursif n aura sa racine carrée prises. C'est l'équivalent de la réduction de moitié de la ci-dessus exposant, donc après k itérations, nous avons que
Nous voulons arrêter quand c'est moins de 2, donnant
Donc après lg lg n itérations de la place de l'enracinement de la récursion s'arrête. Et, depuis, à chaque niveau de la récursivité n'est O(n), le total d'exécution est O(n lg lg n).
Plus généralement, tout comme n'importe quel algorithme à plusieurs reprises des baisses de taille d'entrée dans la moitié devrait vous faire réfléchir "log n," n'importe quel algorithme qui à plusieurs reprises, coupe son entrée d'une taille réduite par la prise d'une racine carrée devrait vous faire réfléchir "log log n.". van Emde Boas arbres utilisation de cette récurrence, par exemple.
Fait intéressant, cette récurrence est utilisé pour obtenir l'exécution d'un célèbre algorithme pour résoudre le plus proche de la paire de points de problème de façon déterministe en supposant que l'ordinateur peut prendre la parole de l'arbitraire d'un nombre réel en temps constant.
En fait, vous pourriez être en mesure d'utiliser le Maître Théorème si vous réécrivez n = 2^(2^k). Dans ce cas, T(n) = √n T(√n) + n devient: T(2^(2^k)) = 2^(2^k-1) T(2^(2^k-1)) + 2^(2^k). Cependant, le 'a' & 'b' ne sont pas constants ici. Je pense qu'il devrait y avoir un moyen, mais ne peut pas penser à tout instant.
Merci pour la grande explication. Lorsque découlant log log n, je pensais que c'était moins compliqué de commencer avec n^(1/(2^k)) = 2, alors levez les deux côtés de (2^k), résultant en n = 2^(2^k), qui devient alors log log n = k comme ci-dessus.
tout ce que vous avez dit est pour T(sqrt n), mais il y a un (sqrt n) dans la multiplication par T(sqrt n).L'habitude qu'être pris en compte?
Je l'ai eu merci....
OriginalL'auteur templatetypedef