Tema
Recurrencias y teorema maestro
- Algoritmos
- Nivel intermedio
El teorema maestro resuelve recurrencias de la forma T(n) = a T(n/b) más f(n) comparando el trabajo que se acumula en las hojas con el trabajo que cuesta partir y combinar.
Nombre en inglés
Recurrences and the master theorem
Intuición
El árbol de llamadas reparte el trabajo por niveles: Arriba hay una tarea grande y abajo hay muchas pequeñas. El teorema compara el coste total de las hojas, que vale n elevado a log_b(a), con el coste de la partición f(n), y gana el mayor de los dos. Cuando empatan aparece un factor logarítmico.
Fórmula
T(n) = a T(n/b) + f(n) ; sea c = log_b(a) ; si f(n) = O(n^{c-e}) entonces T(n) = Theta(n^c) ; si f(n) = Theta(n^c) entonces T(n) = Theta(n^c log n) ; si f(n) = Omega(n^{c+e}) y a f(n/b) <= k f(n) entonces T(n) = Theta(f(n))
Ejemplo resuelto
La ordenación por mezcla cumple T(n) = 2 T(n/2) más n. Aquí a vale 2, b vale 2 y log_2(2) vale 1, de modo que n elevado a 1 coincide con f(n) igual a n y se cae en el caso de empate: El resultado es Theta(n log n). La búsqueda binaria cumple T(n) = T(n/2) más 1, con log_2(1) igual a 0, y el empate con la constante da Theta(log n).
Errores frecuentes
- Aplicar el teorema a recurrencias que no tienen esa forma: La recurrencia T(n) = T(n menos 1) más n no divide el tamaño, así que se resuelve desplegándola y da Theta(n^2).
- Equivocar a con b: El primero cuenta cuántas llamadas se hacen y el segundo en cuánto se reduce el tamaño, y en la búsqueda binaria valen 1 y 2.
- Olvidar la condición de regularidad del tercer caso: Sin ella el teorema no se aplica, y existen recurrencias que caen entre dos casos y quedan fuera de su alcance.
Ejercicio
Resuelva la recurrencia T(n) = 4 T(n/2) más n.
Ver la solución
Con a igual a 4 y b igual a 2, el exponente log_2(4) vale 2. Como f(n) igual a n crece menos que n al cuadrado, domina el trabajo acumulado en las hojas.
Respuesta: Theta(n^2)