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

Question

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

Вот мой старт, в значительной степени crib'd из Википедии, с, конечно, большим запасом мощности.Важно отметить, что это решение будет детонировать для любого особенно большого фиба, и оно содержит относительно наивное использование функции power, которая в худшем случае помещает ее в 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);

}

* Я знаю, язнаете, этого достаточно для любого практического использования, которое имеет Фибоначчи.

Answer 1

Вот почти O(1) решение для члена последовательности Фибоначчи. Следует признать, что O(log n) зависит от реализации системы Math.pow (), но это Фибоначчи без видимого цикла, если ваш интервьюер ищет это. ceil() было связано с точностью округления при больших значениях, возвращающих 0,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);
}

Answer 2

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

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

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

Answer 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).Конечно, это не константа, но я думаю, что стоит добавить к обсуждению, особенно учитывая, что он использует только относительно быстрые целочисленные операции и не имеет возможности округления ошибки.

Answer 5

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

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

Answer 6

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