Can a Fibonacci function be written to execute in O(1) time?

So, we see a lot of fibonacci questions. I, personally, hate them. A lot. More than a lot. I thought it'd be neat if maybe we could make it impossible for anyone to ever use it as an interview question again. Let's see how close to O(1) we can get fibonacci.

Here's my kick off, pretty much crib'd from Wikipedia, with of course plenty of headroom. Importantly, this solution will detonate for any particularly large fib, and it contains a relatively naive use of the power function, which places it at O(log(n)) at worst, if your libraries aren't good. I suspect we can get rid of the power function, or at least specialize it. Anyone up for helping? Is there a true O(1) solution, other than the finite* solution of using a look-up table?

http://ideone.com/FDt3P

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

}

*I know, I know, it's enough for any of the zero practical uses fibonacci has.

25
задан Gilles 'SO- stop being evil' 26 July 2011 в 11:20
поделиться

2 ответа

Следующий ответ выполняет в 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;
}
15
ответ дан 28 November 2019 в 17:46
поделиться

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

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

1
ответ дан 28 November 2019 в 17:46
поделиться
Другие вопросы по тегам:

Похожие вопросы: