Relaciones de Recurrencia

Las relaciones de recurrencia expresan el tiempo de ejecución de un algoritmo recursivo en términos de su tiempo de ejecución en entradas más pequeñas; su resolución produce los límites asintóticos de forma cerrada utilizados para analizar algoritmos de "divide y vencerás" y otros algoritmos recursivos.

Definition

Una relación de recurrencia es una ecuación que define el valor de una función en una entrada en términos de sus valores en entradas más pequeñas; en el análisis de algoritmos, expresa el costo de un algoritmo en una entrada de tamaño n en términos de su costo en subproblemas más pequeños.

Scope

Este tema abarca la formulación y solución de recurrencias que surgen en el análisis de algoritmos: el método de sustitución, el método del árbol de recursión y el teorema maestro para recurrencias de "divide y vencerás" de la forma T(n) = aT(n/b) + f(n). Explica cómo cada algoritmo recursivo induce una recurrencia y cómo traducir esa recurrencia en un límite de "big-Theta". Excluye la notación asintótica en sí, que se trata por separado, y los métodos de funciones generadoras combinatorias de las matemáticas discretas.

Core questions

• ¿Cómo un algoritmo recursivo da lugar a una recurrencia para su tiempo de ejecución?
• ¿Cómo se utiliza el método de sustitución para probar y verificar una solución supuesta?
• ¿Cómo el método del árbol de recursión expone el trabajo total a través de los niveles de recursión?
• ¿Cuándo se aplica el teorema maestro y qué significan sus tres casos?
• ¿Cómo se manejan las recurrencias que quedan fuera de la forma del teorema maestro?

Key concepts

• relación de recurrencia
• método de sustitución
• método del árbol de recursión
• teorema maestro
• recurrencia de divide y vencerás
• caso base y caso recursivo
• solución de forma cerrada
• método de Akra-Bazzi

Key theories

Teorema maestro

Para las recurrencias de "divide y vencerás" T(n) = aT(n/b) + f(n), el teorema maestro proporciona la solución asintótica al comparar f(n) con n elevado a la potencia logaritmo en base b de a, cubriendo los tres casos en los que dominan las hojas, la raíz o los niveles equilibrados.

Métodos del árbol de recursión y de sustitución

El método del árbol de recursión suma el trabajo realizado en cada nivel de recursión para sugerir un límite, que el método de sustitución luego prueba rigurosamente por inducción; juntos manejan recurrencias que van más allá del alcance del teorema maestro.

Clinical relevance

La resolución de recurrencias es la vía estándar para determinar el tiempo de ejecución de algoritmos recursivos, desde "mergesort" y "quicksort" hasta la multiplicación rápida y muchos programas dinámicos. Ingenieros e investigadores utilizan rutinariamente el teorema maestro para derivar y justificar las afirmaciones de complejidad asintótica asociadas a dichos algoritmos.

History

El análisis de recurrencias de algoritmos fue sistematizado en "The Art of Computer Programming" de Knuth. El teorema maestro se convirtió en un pilar de los libros de texto a través de CLRS, y el método de Akra-Bazzi (1998) lo generalizó a una clase más amplia de recurrencias de "divide y vencerás" con divisiones desiguales.

Key figures

• Donald Knuth
• Mohamad Akra
• Louay Bazzi

Seminal works

• cormen2009
• knuth1997vol1

Frequently asked questions

¿Cuándo puedo usar el teorema maestro?

El teorema maestro se aplica a recurrencias de la forma T(n) = aT(n/b) + f(n) con a >= 1 y b > 1, donde cada nivel divide el problema en 'a' subproblemas de tamaño n/b. Las recurrencias con divisiones desiguales, tamaños de subproblemas variables o costos de combinación no polinómicos pueden requerir los métodos del árbol de recursión, de sustitución o de Akra-Bazzi en su lugar.

¿Por qué la recurrencia de "mergesort" da O(n log n)?

Mergesort produce T(n) = 2T(n/2) + O(n): dos subproblemas de la mitad del tamaño más una fusión lineal. Aquí, el trabajo por nivel es el mismo en todos los niveles log n del árbol de recursión, por lo que el total es n veces log n, lo que el teorema maestro confirma como Theta(n log n).