3 implementaciones de Fibonacci

sábado, 1 de noviembre de 2008
En la charla sobre técnicas algorítmicas usé el algoritmo para calcular números de Fibonacci para mostrar como se podía mejorar la eficiencia de un programa utilizando la técnica de programación dinámica. El algoritmo trivial de Fibonacci utiliza recursión múltiple. Esto produce una cantidad exponencial de llamadas, lo que resulta en un algoritmo de complejidad O(2n).
def fibo1(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo1(n-1) + fibo1(n-2)
La técnica de Programación Dinámica consiste en resolver primero subproblemas que están contenidos dentro del problema total, y luego servirse de las soluciones a los subproblemas para resolver el problema total.

Un ejemplo sencillo es el problema de obtener un camino mínimo entre dos puntos. El popular algoritmo de Dijkstra para caminos mínimos utiliza la técnica de programación dinámica.

Para el caso de Fibonacci, los subproblemas son los números de Fibonacci más pequeños que el que queremos calcular. En la implementación anterior, estos números se obtienen con llamadas recursivas. Sin embargo, si comenzamos calculando desde los números de Fibonacci más pequeños y con ellos vamos construyendo los más grandes, se puede realizar el cálculo en O(n).
def fibo2(n):
  if n == 0 or n == 1:
      return 1
  else:
      nm1 = 1
      nm2 = 1
      i = 1
      while i < n:
          nm1, nm2 = nm2, nm1 + nm2
          i = i+1
      return nm2
Un tiempo después Fede me comentaba sobre un algoritmo de Divide & Conquer que permite calcular aún más rápido los números de Fibonacci.

El algoritmo se basa en la siguiente identidad (donde Fn es el enésimo término de la sucesión o secuencia de Fibonacci):



Como existe un algoritmo de Divide & Conquer para elevar un número (o en este caso, una matriz) a una cierta potencia, nos podemos servir de él. Este algoritmo de potenciación es la función aLaN() en el código que sigue. Gracias al mismo, podemos calcular números de Fibonacci en tiempo O(log n).
def fibo3(n):
    # esta funcion multiplica 2 matrices de 2x2
    def multiplicar(m, n):
        return [m[0]*n[0]+m[1]*n[2],
                m[0]*n[1]+m[1]*n[3],
                m[2]*n[0]+m[3]*n[2],
                m[2]*n[1]+m[3]*n[3]]
    # esta funcion eleva una matriz de 2x2 a la k
    # usando el algoritmo de D&C
    def aLaN(m, k):
        if k == 0:
            return [1,0,0,1]
        elif k == 1:
            return m
        else:
            if k % 2 == 0:
                return aLaN(multiplicar(m,m),k/2)
            else:
                return multiplicar(aLaN(multiplicar(m,m),k/2),m)
    
    inicial = [1,1,1,0]
    return aLaN(inicial, n)[0]
Esto permite ver que el correcto uso de técnicas algorítmicas puede mejorar sustancialmente el rendimiento de los algoritmos. Si bien el programa presentado es de juguete, el conocimiento de estas técnicas puede abrir nuevas posibilidades a la hora de desarrollar software.

1 comentario:

daniel dijo...

gracias muy importante tu aporte

Publicar un comentario