viernes, 11 de febrero de 2011

Funcion Fibonacci en Java, con Complejidad O(n)


Es común encontrar la función de fibonacci expresada como F(n) = F(n-1) + F(n-2) , pero en programación la implementacion de dicha función de forma recursiva resulta impractica, debido a la cantidad de recursos que el sistema deberia utilizar para poder calcular valores relativamente pequeños de dicha función (como F(50)), por lo cual es conveniente implementar dicha función, como un ciclo que nos reporta una complejidad lineal y no exponencial.


public static long fibonacci( long pNum ) {
        
        if( pNum == 0 ) {
            return 0;
        }
        
        if( pNum == 1 ) {
            return 1 ; 
        }
                
        long f1 = 1 ;
        long f2 = 0 ;
        
        long f = 0 ;
            
        for( int i = 1 ; i < pNum ; i++ ) {

            f = f1 + f2 ;        
            
            f2 = f1 ;
            
            f1 = f ;
                        
        }
        
        return f;
        
    }

1 comentario:

  1. Viendo el algoritmo por lo menos deberías de hacer que el ciclo empiece en 2 para hacer una suma menos, incluso lo podes hacer que empiece en 3 y hacer que devuelva 1 cuando el valor inicial de n sea 2 ya que eso iría dentro del mismo if que colocaste anteriormente.

    ResponderEliminar