[2] Resolver una relación de recurrencia consiste en determinar una fórmula explícita (cerrada) para el término general
, es decir una función no recursiva de n. Hay tres métodos para resolver relaciones recurrentes: iteración, transformada Z y un método especial que se aplica a las relaciones de recurrencia lineales homogéneas con coeficientes constantes.
Un ejemplo de una relación de recurrencia es el siguiente: Algunas definiciones de recurrencia pueden tener relaciones muy complejas (caóticas), y sus comportamientos a veces son estudiados por los físicos y matemáticos en un campo conocido como análisis no lineal.
La forma más sencilla para resolver una relación de recurrencia es formular una posible solución (hipótesis) y comprobar por inducción la validez de la misma.
está dado por la siguiente ecuación de recurrencia: Resolver la recurrencia sería encontrar la ecuación que nos da el valor de
[3] Para resolver una relación de recurrencia asociada a la sucesión:
por iteración, utilizamos la relación de recurrencia para escribir el n-ésimo término
Continuamos hasta llegar a alguno de los casos base.
el orden es dos, porque debe haber al menos dos términos anteriores (ya sean usados o no).
Ejemplos : Se llama ecuación de recurrencia lineal homogénea de orden k, con coeficientes constantes, a una expresión del tipo: Para poder encontrar una solución, hacen falta unas condiciones de contorno o iniciales
Sea la ecuación de recurrencia lineal homogénea de orden k anterior, se denomina ecuación característica a la ecuación de grado k: Las secuencias lineales recursiva son precisamente las secuencias cuya función de generación es una función racional: el denominador es el polinomio auxiliar (a una transformación), y el numerador se obtiene con los valores iniciales.
El caso más sencillo son las secuencias periódicas,
, una transformación del polinomio auxiliar (equivalente, invirtiendo el orden de los coeficientes); también se puede usar cualquier múltiplo de esta, pero esta normalización es elegida por ambas porque la relación simple del polinomio auxiliar, y de ese modo
el polinomio de grado menor o igual que
La ecuación característica es la siguiente: por lo tanto, la solución general es: Para hallar el valor de
es la solución particular que depende de la función F(n).
Por lo tanto los pasos a seguir serían, primero calcular la solución de la ecuación homogénea, calcular una solución particular para F(n) y sumarla a la homogénea, y a continuación aplicar las condiciones iniciales para calcular las constantes.
Para resolver recurrencias no lineales tenemos muchas opciones de las cuales: La conexión con el análisis de algoritmos estriba en que la forma que se ha adoptado para medir las complejidades, utiliza funciones cuyo dominio son los números naturales, o en otras palabras, sucesiones.
En un algoritmo recursivo, la función t(n) que establece su complejidad viene dada por una ecuación de recurrencia.
Una ecuación de recurrencia nos permiten indicar el tiempo de ejecución para los distintos casos del algoritmo recursivo (casos base y recursivo).
Considerando el producto como operación básica, podemos construir la ecuación recurrente para calcular la complejidad del algoritmo como sigue: Como se ve en el código el caso base es para n<=1, para estos valores de n el número de multiplicaciones que se realiza es 0.
Y en otro caso es 1 más las necesarias para calcular el factorial de n-1.
Así construimos la función recurrente: Ahora si resolvemos la ecuación recurrente sabremos la complejidad de este algoritmo en función de n. Procedemos a resolver esta ecuación recurrente no lineal: resolvemos la homogénea: resolvamos ahora la particular: como la particular' coincide con la r, debemos aumentar el grado multiplicando por n por lo que la solución de la ecuación recurrente queda como sigue: Ahora calculamos c utilizando el caso base, t(1) = 1 ya tenemos la solución: t(n) = n La ecuación que nos ha quedado es de grado 1 por lo que la complejidad es del orden exacto de n -> θ(n) Por ejemplo para calcular el factorial de 3 necesitaremos t(3) productos lo que es igual a Como vemos son 2 productos como nos ha devuelto la ecuación.
En este contexto, a menudo se utilizan ecuaciones de diferencias acopladas para modelar la interacción de dos o más poblaciones.
Estas y otras ecuaciones de diferencias son particularmente adecuadas para modelar poblaciones univoltinas.
Si un algoritmo está diseñado para que rompa un problema en subproblemas más pequeños divide y vencerás, su tiempo de ejecución se describe por una relación de recurrencia.
El peor escenario posible es cuando el elemento requerido es el último, por lo que el número de comparaciones es {N} .
Un algoritmo mejor se llama búsqueda binaria.
Comprueba primero si el elemento está en el centro del vector.
En este punto, la mitad del vector puede ser descartada, y el algoritmo puede ser ejecutado de nuevo en la otra mitad.