由网友(宁乡小王子)分享简介：有没有什么算法来计算子线性时间的第n个斐波纳契数？Is there any algorithm to compute the nth fibonacci number in sub linear time?推荐答案在 N 个斐波那契数由f(n) = Floor(phi^n / sqrt(5) + 1/2)其中...

有没有什么算法来计算子线性时间的第n个斐波纳契数？

Is there any algorithm to compute the nth fibonacci number in sub linear time?

推荐答案

在 N 个斐波那契数由

f(n) = Floor(phi^n / sqrt(5) + 1/2)

其中

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

假设基本数学运算（ + ， - ， * 和 / ）的 O（1）您可以用这个结果来计算 N 日在 O（log n）的时间（ O（log n）的因为式中的求幂的）。

Assuming that the primitive mathematical operations (+, -, * and /) are O(1) you can use this result to compute the nth Fibonacci number in O(log n) time (O(log n) because of the exponentiation in the formula).

在C＃：

In C#:

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}