次线性时间内的第 n 个斐波那契数 [英] nth fibonacci number in sublinear time

问题描述

是否有任何算法可以在亚线性时间内计算第 n 个斐波那契数?

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

推荐答案

nth Fibonacci number is given by

The nth Fibonacci number is given by

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

哪里

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

假设原始数学运算(+、-、* 和 /)为 O(1) 你可以使用这个结果在 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# 中:

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

这篇关于次线性时间内的第 n 个斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！