algorithm - serie - sucesion de fibonacci ejercicios

¿Se puede escribir una función de Fibonacci para que se ejecute en O(1) tiempo?

Question

Por lo tanto, vemos muchas preguntas de fibonacci. Yo, personalmente, los odio. Mucho. Más que mucho. Pensé que sería genial si pudiéramos hacer imposible que alguien lo use como una pregunta de entrevista nuevamente. Veamos qué tan cerca de O (1) podemos obtener fibonacci.

Aquí está mi punto de partida, más o menos de Wikipedia, con mucho espacio para la cabeza. Es importante destacar que esta solución detonará para cualquier fib particularmente grande, y contiene un uso relativamente ingenuo de la función de poder, que la coloca en O (log (n)) en el peor de los casos, si sus bibliotecas no son buenas. Sospecho que podemos deshacernos de la función de poder, o al menos especializarla. ¿Alguien está dispuesto a ayudar? ¿Existe una verdadera solución O (1), aparte de la solución finita * de usar una tabla de consulta?

http://ideone.com/FDt3P

#include <iostream>
#include <math.h>
using namespace std; // would never normally do this.

int main()
{
int target = 10;
cin >> target;
// should be close enough for anything that won''t make us explode anyway.
float mangle = 2.23607610; 

float manglemore = mangle;
++manglemore; manglemore = manglemore / 2;
manglemore = pow(manglemore, target);
manglemore = manglemore/mangle;
manglemore += .5;
cout << floor(manglemore);

}

* Lo sé, lo sé, es suficiente para cualquiera de los cero usos prácticos que tiene fibonacci.

Answer 1

Aquí hay una solución cercana a O(1) para un término de secuencia de Fibonacci. Es cierto que O(log n) dependiendo de la implementación del sistema Math.pow (), pero es Fibonacci w / oa loop visible, si su entrevistador está buscando eso. El ceil() se debió a la precisión de redondeo en valores más grandes que devolvieron .9 repetición.

Ejemplo en JS:

function fib (n) {
  var A=(1+Math.sqrt(5))/2,
      B=(1-Math.sqrt(5))/2,
      fib = (Math.pow(A,n) - Math.pow(B,n)) / Math.sqrt(5);
      return Math.ceil(fib);
}

Answer 2

Dadas entradas grandes arbitrarias, simplemente leer en n toma O (log n), por lo que en ese sentido no es posible un algoritmo de tiempo constante. Por lo tanto, use la solución de formulario cerrado o calcule los valores que le interesan para obtener un rendimiento razonable.

Edit: En los comentarios, se señaló que en realidad es peor, porque fibonacci es O(phi^n) imprimiendo el resultado de Fibonacci es O(log (phi^n)) que es O(n) !

Answer 3

Elija un valor más grande para manejar. Para cualquier valor mayor, levante un error. Para cualquier valor más pequeño que eso, simplemente almacene la respuesta en ese valor más pequeño, siga ejecutando el cálculo para el valor "más grande" y devuelva el valor almacenado.

Después de todo, O(1) significa específicamente "constante", no "rápido". Con este método, todos los cálculos tomarán la misma cantidad de tiempo.

Answer 4

En Programación: La derivación de algoritmos , Anne Kaldewaij amplía la solución de álgebra lineal para obtener (traducida y refactorizada del lenguaje de programación usado en ese libro):

template <typename Int_t> Int_t fib(Int_t n)
{
    Int_t a = 0, b = 1, x = 0, y 1, t0, t1;
    while (n != 0) {
        switch(n % 2) {
            case 1:
                t0 = a * x + b * y;
                t1 = b * x + a * y + b * y;
                x = t0;
                y = t1;
                --n;
                continue;
            default:
                t0 = a * a + b * b;
                t1 = 2 * a * b + b * b;
                a = t0;
                b = t1;
                n /= 2;
                continue;
        }
    }
    return x;
}

Esto tiene complejidad O (log n). Eso no es constante, por supuesto, pero creo que vale la pena agregar a la discusión, especialmente dado que solo usa operaciones enteras relativamente rápidas y no tiene posibilidad de redondeo de errores.

Answer 5

La siguiente respuesta se ejecuta en O (1), aunque no estoy seguro de si está calificado para su pregunta. Se llama Plantilla Meta-Programación .

#include <iostream>
using namespace std;

template <int N>
class Fibonacci
{
public:
    enum {
        value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value
    };
};

template <>
class Fibonacci<0>
{
public:
    enum {
        value = 0
    };
};

template <>
class Fibonacci<1>
{
public:
    enum {
        value = 1
    };
};

int main()
{
    cout << Fibonacci<50>::value << endl;
    return 0;
}

Answer 6

Sí. Precalcular los valores, y almacenar en una matriz, luego usar N para hacer una búsqueda.