math - Resolviendo la relación de recurrencia T(n)=√n T(√n)+n

recursion complexity-theory

Question

¿Es posible resolver la relación de recurrencia?

T (n) = √n T (√n) + n

¿Usando el teorema maestro? No es de la forma

T (n) = a ⋅ T (n / b) + f (n)

pero este problema se da en el ejercicio del capítulo 4 de CLRS.

Answer 1

Esto no puede ser resuelto por el Teorema Maestro. Sin embargo, puede resolverse utilizando el método de árbol de recursión para resolver O (n log log n).

La intuición detrás de esto es notar que en cada nivel del árbol, estás haciendo n trabajo. El nivel superior no funciona explícitamente. Cada uno de los subproblemas √n funciona √n para un total neto de n trabajo, etc. Entonces, la pregunta ahora es qué tan profundo es el árbol de recursión. Bueno, esa es la cantidad de veces que puedes tomar la raíz cuadrada de n antes de que n sea lo suficientemente pequeña (digamos, menos de 2). Si escribimos

n = 2 ^{lg n}

luego en cada llamada recursiva n se tomará su raíz cuadrada. Esto es equivalente a reducir a la mitad el exponente anterior, así que después de k iteraciones tenemos que

n ^{1 / (2 k )} = 2 ^{lg n / (2 k )}

Queremos parar cuando esto sea menos de 2, dando

2 ^{lg n / (2 k )} = 2

lg n / (2 ^k ) = 1

lg n = 2 ^k

lg lg n = k

Entonces, después de lg lg n iteraciones de enraizamiento cuadrado, la recursión se detiene. Y, dado que en cada nivel la recursión funciona O (n), el tiempo de ejecución total es O (n lg lg n).

De manera más general, así como cualquier algoritmo que recorta repetidamente su tamaño de entrada a la mitad debería hacerte pensar "log n", cualquier algoritmo que recorta repetidamente su tamaño de entrada tomando una raíz cuadrada debería hacerte pensar "log log n". Los árboles de van Emde Boas usan esta recurrencia, por ejemplo.

Curiosamente, esta recurrencia se utiliza para obtener el tiempo de ejecución de un algoritmo famoso para resolver el problema del par de puntos más cercano de forma determinista suponiendo que la computadora puede tomar el piso de un número real arbitrario en tiempo constante.