Solución de recurrencias
-
19-09-2019 - |
Pregunta
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 que resulta ser n/(log(n/9))
.
¿Puedo generalizar la ecuación anterior en la forma de n.loglogn
Esta es una duda general, no tengo, necesito una visión sobre esto.
Nota:
Cualquier función que tiene que ser Theta(n^k log^k (n))
en que la función de k debe> = 1. Y en este caso es k -1 de manera teorema maestro no viene en imaginar
Solución
Es cierto, el teorema del Maestro no se aplica.
T (n) = 3T (n / 3) + n / logn.
Sea g (n) = T (n) / n.
A continuación, 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 / (log n -1) + 1 / (log n - 2) + ...) = Theta (Integral 1 / x entre 1 y logn) = Theta (log log n ).
Por lo tanto T (n) = n g (n) = Theta (n logn log.)
Lo has adivinado bien.
Otros consejos
Si utiliza un árbol para visualizar la pregunta, verá que la suma de cada rango es:
- rango 0:
(que es igual a n / log (n)) - rank 1:
y así sucesivamente, con una suma general de n/log(n/(3^i))
para cada rango, siendo i el rango actual. así, todos juntos tenemos:
si abrimos la ecuación obtenemos:
(empezando desde el extremo y va hacia atrás .. primero cuando i = log (BASE 3) n y luego volver)
desde la base de registro no importa en theta, obtenemos:
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:
así, es theta (n log log n).