Можно ли записать функцию Фибоначчи для выполнения в O (1) раз?

Итак, мы видим много вопросов о фибоначчи. Я лично их ненавижу. Много. Больше, чем много. Я думал, что это будет аккуратно, если, возможно, мы сможем сделать невозможным когда-либо использовать его снова как вопрос интервью. Посмотрим, как близко к O (1) мы можем получить фибоначчи.

Здесь мой удар, довольно много извинился из Википедии, с, конечно, большим запасом. Важно отметить, что это решение будет взорваться для любого особо большого фига, и оно содержит относительно наивное использование силовой функции, которая в худшем случае помещает ее в O (log (n)), если ваши библиотеки не очень хороши. Я подозреваю, что мы можем избавиться от силовой функции или хотя бы специализировать ее. Кто-нибудь за помощь? Существует ли истинное решение O (1), отличное от конечного * решения использования справочной таблицы?

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

}

* Я знаю, я знаю, этого достаточно для любого из нулевых практических применений, связанных с фибоначчи.

Ответ 1

Учитывая произвольные большие входы, просто чтение в n принимает O (log n), поэтому в этом смысле не существует алгоритма постоянного времени. Таким образом, используйте закрытое решение формы или предопределите ценности, которые вам нужны, чтобы получить разумную производительность.

Изменить: в комментариях было указано, что на самом деле это хуже, потому что фибоначчи O(phi^n) печатает результат Фибоначчи O(log (phi^n)), который O(n)!

Ответ 2

Вот приблизительное решение O(1) для термина последовательности Фибоначчи. По общему признанию, O(log n) в зависимости от реализации системы Math.pow(), но это Fibonacci без видимого цикла, если ваш интервьюер ищет это. ceil() был вызван точностью округления при больших значениях, возвращаемых .9 повторение.

Пример в 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);
}

Ответ 3

Следующий ответ выполняет в O (1), хотя я не уверен, соответствует ли он вам вопрос. Он называется Мета-программирование шаблонов.

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

Ответ 4

В программировании: "Вывод алгоритмов" Энн Калдейлай расширяет решение линейной алгебры, чтобы получить (перевести и реорганизовать с языка программирования в этой книге):

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

Это сложность O (log n). Это, конечно, не постоянное, но я думаю, что стоит добавить к обсуждению, особенно учитывая, что он использует относительно быстрые целые операции и не имеет возможности ошибки округления.

Ответ 5

Да. Предварительно расчитайте значения и сохраните в массиве, затем используйте N для поиска.

Ответ 6

Выберите какое-то самое большое значение для обработки. Для любого большего значения поднимите ошибку. Для любого меньшего значения, чем это, просто сохраните ответ с меньшим значением и продолжайте вычисление для "наибольшего" значения и верните сохраненное значение.

В конце концов, O(1) означает "постоянный", а не "быстрый". При таком методе все вычисления будут занимать одинаковое количество времени.

Ответ 7

Фибоначчи в O (1) пространстве и времени (реализация Python):

PHI = (1 + sqrt(5)) / 2

def fib(n: int):
  return int(PHI ** n / sqrt(5) + 0.5)