Résolution récurrences
-
19-09-2019 - |
Question
essaie de résoudre le récursion donné, en utilisant l'arbre de récursivité, T(n) = 3T(n/3) + n/lg n.
Dans le premier niveau (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3))
.
Dans le deuxième niveau, il se révèle être n/(log(n/9))
.
je peux généraliser l'équation ci-dessus sous la forme d'n.loglogn
Ceci est un doute général je l'ai, je besoin d'un aperçu sur ce point.
Note:
Toute fonction qui doit être Theta(n^k log^k (n))
dans cette fonction k devrait> = 1. Et dans ce cas k est -1 si le théorème de maître ne vient pas à l'image
La solution
Il est vrai, le théorème de Maître ne s'applique pas.
T (n) = 3T (n / 3) + n / logn.
Soit g (n) = T (n) / n.
Alors n g (n) = 3 (n / 3) * g (n / 3) + n / logn.
Ainsi
g (n) = g (n / 3) + 1 / log n.
Cela donne g (n) = Somme 1 / log n + 1 / log n / 3 + 1 / log n / 9 + ...
= Theta (Somme 1 / logn + 1 / (log n -1) + 1 / (log n - 2) + ...) = Theta (Intégral 1 / x compris entre 1 et logn) = Theta (log log n ).
Ainsi T (n) = n g (n) = Theta (n log log n.)
Vous l'aurez deviné droit.
Autres conseils
Si vous utilisez un arbre pour visualiser la question, vous verrez que la somme de chaque rang est:
- rang 0:
(qui est égale à n / log (n)) - Rang 1:
et ainsi de suite, avec un total général de n/log(n/(3^i))
pour chaque rang, i étant le rang courant. donc, tous ensemble, nous obtenons:
si nous ouvrons l'équation que nous obtenons:
(à partir de la fin et revenir en arrière .. d'abord quand i = log (Base3) n, puis retourner)
puisque la base du journal n'a pas d'importance dans thêta, nous obtenons:
qui est:
qui est (en sigma):
qui est une série harmonique, égale à:
et puisque ln log avec une base de e et log bases ne comptent pas thêta, nous avons finalement obtenir:
qui est égale à:
ainsi, il est thêta (n log log n).