Fibonacci函数可以写入在O(1)时间内执行吗？

Question

所以,我们看到了很多斐波纳契问题.我个人非常讨厌他们.很多.不止一切.我认为如果我们可以让任何人都不可能再次将其用作面试问题,那就太好了.让我们看看有多接近O(1)我们可以得到斐波那契.

这是我的开始,几乎来自维基百科,当然还有足够的空间.重要的是,这个解决方案将引爆任何特别大的fib,它包含一个相对天真的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)Fibonacci序列项的近似解.不可否认,O(log n)取决于系统Math.pow()的实现,但如果您的面试官正在寻找,那么它就是Fibonacci w/o可见循环.这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);
}

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

在《编程：算法的推导》中，Anne Kaldewaij扩展了线性代数解，以得到（从那本书中使用的编程语言进行翻译和重构）：

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）复杂度。当然，这不是恒定的，但是我认为值得增加讨论，特别是考虑到它仅使用相对较快的整数运算并且没有舍入误差的可能性。