能否在常数时间内计算isFibonacci()？

Question

可以根据这里描述的方法创建一个快速的“给出第n个斐波那契数”的函数。是否有一种方法编写O（1）性能的isFibonacci(int i)函数？

我可以预先计算值。但是，计算需要O（n）时间，我无法为大数进行计算。

- DIBits

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

- Phenomenal One

---

“isPerfectSquare” 怎样能够在常数时间内实现？ - harold

@harold return round(sqrt(n))^2 == n; @哈罗德 返回 round(sqrt(n))^2 == n; - DIBits

@哈罗德 或者类似于 return isInteger(sqrt(n)) - DIBits

@DIBits 但这不是常数时间。它是 sqrt(n)。 - nice_dev