Una relación de recurrencia cuando diseñamos algoritmos típicamente (la mayoría de las veces) es una función de crecimiento que representa el tiempo de ejecución del algoritmo con respecto al tamaño de entrada para un tipo particular de análisis (por ejemplo, el peor de los casos). Usualmente lo formulamos como una función que se escribe en términos de sí misma (caso recursivo) y un valor constante cuando la entrada es pequeña (caso base).
Algo así como [matemática] T (n) = T (n / 2) + 1 [/ matemática] cuando [matemática] n> 1 [/ matemática], [matemática] T (1) = 1 [/ matemática] podría representar el tiempo de ejecución de un algoritmo como la búsqueda binaria en el peor de los casos. Lo llamamos recurrencia porque se define por sí mismo, recursivamente. Esto ocurre con mucha frecuencia en el análisis de los algoritmos Divide and Conquer.
Las recurrencias no solo ocurren dentro del contexto de nuestro campo, y se estudian ampliamente en todas las disciplinas matemáticas y más allá.
- ¿Cuáles son los posibles algoritmos utilizados en los juegos de carrera sin fin?
- ¿Cuál es la lógica detrás de los algoritmos de ajuste de aprendizaje automático?
- ¿Por qué se usa el sistema binario?
- ¿Cuáles son los mejores libros sobre algoritmos y estructuras de datos?
- ¿Qué es un árbol rojo-negro?
Para obtener más información, consulte Relación de recurrencia – Wikipedia.
