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

Question

可以创建一个快速 "give n-th fibonacci number" 函数，如 here 所述。有没有办法编写一个在 O(1) 中执行的 isFibonacci(int i) 函数？

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

Answer 1

一个数字是斐波那契当且仅当 (5*n² + 4) 或 (5*n^{2[=15= 中的一个或两个] – 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); 
}