algorithm - 是否可以在恒定时间内计算 Fibonacci()？

Question

可以创建一个快速的“给出第 n 个斐波那契数”函数，如所述 here .有没有一种方法可以编写在 O(1) 中执行的 isFibonacci(int i) 函数？

我可以预先计算值。但是计算最后一个 O(n)，我不能对大数进行计算。

Answer 1

一个数是斐波那契当且仅当 (5*n² + 4) 或 (5*n² – 4) 中的一个或两个是一个完美的正方形.

bool isFibonacci(int n) 
{ 
    // n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both 
    // is a perferct square 
    return isPerfectSquare(5*n*n + 4) || 
           isPerfectSquare(5*n*n - 4); 
}