La complejidad de algoritmos recursivos involucra la solución de una ecuación diferencial. El método mas simple es adivinar una solución y verificar si esta bien la adivinanza.
Recurrencia matemática: Define una función en f términos de ella misma. En el ejemplo del factorial de un numero natural, tenemos: n! = n (n-1).
En el ejemplo de los números Fibonacci
Fn = Fn-1 + Fn-2 ; n >= 2
F0 = 0
F1 = 1
(Donde n, 1, 0 son las bases de F).
Algoritmo factorial recursivo
Dado n
Factorial n*F(n-1)
devolver factorial
Procedimiento F(k)
Si k=0 o 1 entonces devolver 1
caso contrario devolver k*F(k-1)
La complejidad de un algoritmo recursivo se expresa a través de una ecuación de recurrencia:
Sea T(n) = tiempo para calcular n!, entonces:
T(n) = T(n-1) + 1 ; si n >= 1
T(1) = 1
Si resolvemos de una manera mas sencilla esta ecuación tenemos:
T(n) = T(n-1) + 1
T(n) = (T(n-2)+1)+1 = T(n-2) + 2
T(n) = ((T(n-3)+1)+1)+1 = T(n-3) + 3
'
'
'
T(n) = T(n-k) + k
'
'
T(n) = T(1) + n-1
T(n) = T(0) + n = n
Luego la complejidad del algoritmo factorial recursivo es ~ O(n).
Reducción por sustracción
Si el tamaño n del problema decrece en una cantidad constante b en cada llamada, se realizan a llamadas recursivas y las operaciones correspondientes a la parte no recursiva del algoritmo toman un tiempo O(n^k) entonces:
T(n) = a T(n-b) + O(n^k) ; si n >= b
La solución de esta ecuación de recurrencia es de la forma:
T(n) = { n^k ; si a < 1
' { n^k+1 ; si a = 1
' { a^n/b ; si a > 1
Reducción por división
T(n) = aT(n/b) + O(n^k) ; si n >= b
La solución de esta ecuación de recurrencia es de la forma:
T(n) = { n^k ; si a < b^k
' { n^k log n ; si a = b^k
' { n^log b a (donde b es la base) ; si a > b^k
Muy bien, seis puntos.
ResponderEliminar