recurrencias Solución de

Question

estoy tratando de resolver el recursividad dado, utilizando la recursividad árbol, T(n) = 3T(n/3) + n/lg n.

En el primer nivel (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).

En el segundo nivel resulta n/(log(n/9)).

¿Puedo generalizar la ecuación anterior en forma de n.loglogn

Ésta es una duda general, no tengo, necesito una visión sobre esto.

Nota: Cualquier función que tenga que ser Theta(n^k log^k (n)) en esa función k debería> = 1. Y en este caso k es -1 por lo que el teorema maestro no entra en la imagen

Answer 1

Es verdad, el teorema del Maestro no se aplica.

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

Let g (n) = T (n)/n.

Luego n g (n) = 3 (n/3) * g (n/3) + n/logn.

Así

g (n) = g (n/3) + 1/log n.

Esto da g (n) = Sum 1/log n + 1/log n/3 + 1/log n/9 + ...

= Theta (Sum 1/logn + 1/(logn -1) + 1/(log n - 2) + ...) = Theta (Integral 1/x entre 1 y logn) = Theta (log log n).

lo tanto T (n) = n g (n) = Theta (n logn log.)

adivinaron derecha.

Answer 2

Si utiliza un árbol para visualizar la pregunta, verá que la suma de cada rango es:

• rango 0:

(el cual es igual n/log (n)) - rango 1:

y así sucesivamente, con una suma general de n/log(n/(3^i)) para cada rango, siendo el rango actual. así, todos juntos tenemos:

si abrimos la ecuación obtenemos:

(empezando por el final y yendo hacia atrás ..por primera vez cuando i = log (BASE 3) n y luego volver)

desde la base de registro no importa en theta, se obtiene:

que es:

que es (en sigma):

que es una serie armónica, igual a:

y desde ln es iniciar sesión con una base de correo e inicie sesión bases no importan en theta, por fin tenemos:

que es igual a:

entonces, es theta (n log log n).