6 Recurrencias - psyepez2005/Analisis_De_Algoritmos GitHub Wiki

Recurrencias

• El tiempo de ejecución de un algoritmo recursivo se representa más fácilmente con una expresión recursiva.
• Una relación de recurrencia define una función usando versiones más pequeñas de sí misma (ejemplo: n!).
• Las ecuaciones de recurrencia se utilizan para encontrar cotas asintóticas en algoritmos recursivos, es decir, cómo crece su tiempo de ejecución a medida que la entrada aumenta.

Método de suposiciones inteligentes:

1. Calcular los primeros valores de la recurrencia.
2. Buscar una regularidad o patrón.
3. Proponer una fórmula general.
4. Verificarla mediante inducción matemática u otro método.

Método de la ecuación característica:

• Se utiliza especialmente en recurrencias lineales con coeficientes constantes.
• Permite obtener una solución cerrada de forma más estructurada.

Talleres hechos en clase