一个 Fibonacci 函数能够被写成 O(1) 时间复杂度吗？

Question

我们经常看到很多斐波那契数列的问题。我个人非常讨厌它们，甚至可以说是非常非常讨厌。我认为如果我们能够使其无法再被用作面试题，那将会很有意义。让我们看看我们能够实现多接近 O(1) 的斐波那契数列。

以下是我从维基百科借鉴的代码，当然还有很大的提升空间。重要的是，这个解决方案对于任何特别大的斐波那契数都会出错，并且其中使用了相对简单的 power 函数，最坏情况下它的时间复杂度为 O(log(n))，如果你的库不好的话。我怀疑我们是否可以摆脱 power 函数，或者至少专门化它。有没有人愿意帮忙？除了使用查找表的有限*解决方案之外，是否存在真正的 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);
}

*我知道，我知道，斐波那契数列在实际应用中几乎没有任何作用。

- Jake Kurzer

---

这需要依赖于幂函数，它不是O(c)。我的例子实际上就是那个算法，而它在我的问题中有所提及。 - Jake Kurzer

似乎最大的问题是pow函数不精确。也许可以将其分割成这样一个方式，使得任何误差都小于1/2，然后四舍五入？然后重复执行？（使用一行数学公式来获取第n个斐波那契数） - soandos

当然可以-只需使用查找表-在1和FLT_MAX之间没有太多的斐波那契数。;-) - Paul R

我会让它变成O(1)... O(c)是常数时间，用于表示它可能不是单个操作。看起来似乎不是标准的，所以... - Jake Kurzer

如果你想进行简单的检查，斐波那契数列的最后几位会形成一个规律（16进制每24个数字重复一次，32进制每48个数字重复一次，64进制每96个数字重复一次等等）。你可以利用这一规律进行更精确的四舍五入。 - soandos

Answer 1

这里是一个接近 O(1) 的斐波那契数列项的解决方案。诚然，O(log n) 取决于系统 Math.pow() 实现，但如果您的面试官需要这样的斐波那契数列而没有可见的循环，那么这就是一个不错的选择。 ceil() 是由于在较大值上舍入精度返回.9重复。

JavaScript 示例：

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

- Joseph Lust

---

不错。适用于n <= 1474。超过这个范围，结果变为无穷大。 - user31389

谢谢你提供这个代码，我一直在寻找这个算法的代码以便于添加到课程演示中。然而，我们使用Java（1.8），而直接翻译此代码会导致样本值（例如10、20、40、45、50）增加1。删除 .ceil() 调用后问题得到解决。 - David Brown

有人能解释一下为什么在其他语言中需要使用 floor 函数吗？我查看了证明，但并没有明显的原因。 - PSub

这应该是最好的答案。 - paullb

实际上，您不必计算B^n，从而使过程更快。 B^n始终小于0.5，因此您可以将公式重写为Fib（n）= round（A ^ n / sqrt（5））。 https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding - Adam Štafa

在Java中，内置的Math.pow()和Math.sqrt()都是O(1)，因此Binet公式的时间复杂度为O(1)。 - Bu Saeed

Answer 2

考虑到处理任意大的输入，仅读取n就需要O(log n)，因此从这个意义上讲，没有常数时间算法是可能的。因此，使用闭式解或预计算所关心的值，以获得合理的性能。

编辑：在评论中指出它实际上更糟糕，因为斐波那契数列的复杂度是O(phi^n)，打印斐波那契数列的结果的复杂度是O(log (phi^n))，这是O(n)！

- Philip JF

---

现在这样也可以，我猜。但是只是草草了事感觉有点不够充分。 - Jake Kurzer

实际上比这更糟糕...确实，读取输入的时间复杂度为O(log n)。 但是，打印（甚至存储）输出无论使用什么进制都是O(n)。（输出值为O(phi^n)，需要O(n)位数字表示。） - Nemo

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

- Dante May Code

---

抠字眼的话，这个操作是在编译时执行的，但并没有花费恒定的时间。 - hammar

@hammar，你无法否认它在 O(1) 的时间内执行。它不能以 O(1) 编译是另一回事。 - Dante May Code

我的观点是这是一个元程序，而元程序在编译时执行。在运行时，它只显示一个常量，确实是O(1)。 - hammar

即使对于我们的目的来说并不完美，它仍然非常聪明。 - Jake Kurzer

我会说很有创意 :-D - NirmalGeo

这并不是一个解决方案，相反，你的编译器程序无法解决这个任务。如果你说你通过编译找到了答案，那么评论者是正确的，因为它在编译时间上不是O(1)。 - unkulunkulu

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)。虽然不是常数级别，但我认为这个信息值得加入讨论，特别是它只使用了相对快速的整数运算，并且没有出现舍入误差的可能。

- Max Lybbert

Answer 5

是的。预先计算值并存储在数组中，然后使用N进行查找。

- EvilTeach

---

我提到了查找表。 - Jake Kurzer

Answer 6

选取一些最大的值进行处理。对于任何比较大的值，抛出错误。对于任何小于该值的较小值，只需将答案存储在该较小值处，并继续计算"最大"值，并返回存储的值。

总之，O(1)具体指的是"恒定"，而不是"快速"。通过这种方法，所有的计算都将花费相同的时间。

- evil otto

Answer 7

斐波那契数列的O(1)空间和时间实现（Python实现）：

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

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

- CCBet

---

你能试试看这需要哪些参数才需要5秒钟、10秒钟、15秒钟、20秒钟、30秒钟、50秒钟、70秒钟以及100秒钟吗？这看起来是线性的吗？结果准确吗？ - greybeard