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;
        
    }