récurrences Solving

Question

essaie de résoudre le récursion donné, en utilisant l'arbre de récursivité, T(n) = 3T(n/3) + n/lg n.

Au 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 s'avère être n/(log(n/9)).

Puis-je généraliser l'équation ci-dessus sous la forme de n.loglogn

C'est un doute général je l'ai, je besoin d'un aperçu sur ce point.

Remarque: Toute fonction qui doit être Theta(n^k log^k (n)) dans cette fonction k doit> = 1. Et dans ce cas k est -1 donc le théorème maître ne vient pas à l'image

Answer 1

Il est vrai que le théorème du Master ne s'applique pas.

T (n) = 3T (n/3) + n/logn.

Soit g (n) = T (n)/n. Puis 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/log n + 1/(logn -1) + 1/(log n - 2) + ...) = Thêta (Integral 1/x entre 1 et logn) = Theta (log log n).

Ainsi T (n) = n g (n) = Theta (n logn log.)

Vous l'avez deviné juste.

Answer 2

Si vous utilisez un arbre pour visualiser la question, vous verrez que la somme de chaque rang est:

• rang 0:

(qui est égal à n/log (n)) - rang 1:

et ainsi de suite, avec une somme générale de n/log(n/(3^i)) pour chaque rang, i étant le rang courant. donc, tous ensemble, nous obtenons:

si nous ouvrons l'équation nous obtenons:

(à partir de la fin et revenir en arrière ..d'abord quand i = log (Base3) n, puis retourner)

depuis 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 obtenons finalement:

qui est égal à:

donc, c'est thêta (n log log n).