让我们来看一下四个不同的函数,使用伪代码计算第n个斐波那契数,而不是限制在单一语言中。第一个遵循标准的递归定义:
function fib(n)
if n <= 2 return 1
return fib(n-1) + fib(n-2)
这个函数需要指数时间,O(2
n),因为它在每一步重新计算之前计算过的斐波那契数。第二个函数需要线性时间,O(
n),通过从1到
n工作而不是从
n到1,并跟踪两个先前的斐波那契数。
function fib(n) # linear
if n <= 2 return 1
prev2 = prev1 = 1
k := 3
while k <= n
fib := prev2 + prev1
prev2 := prev1
prev1 := fib
return fib
这是您程序使用的相同算法,尽管您的方法通过递归操作并通过指向外部变量的指针传递其中一个参数来掩盖正在进行的操作。
Dijkstra 提出了一种计算第n个斐波那契数列数值的算法,使用矩阵和平方取幂算法,时间复杂度为O(log n)。我在这里不会给出完整的解释;Dijkstra做得比我好(尽管您应该注意他的约定,F
0=1而不是我们一直在做的F
0=0)。下面是算法:
function fib(n)
if n <= 2 return 1
n2 := n // 2
if n % 2 == 1 return square(fib(n2+1)) + square(fib(n2))
return fib(n2) * (2*fib(n2-1) + fib(n2))
第四个算法在常数时间内运行,即O(1),前提是您拥有具有足够精度的浮点数,使用斐波那契数的数学定义:
function fib(n)
sqrt5 := sqrt(5)
p := (1 + sqrt5) / 2
q := 1 / p
return floor((p**n + q**n) / sqrt5 + 0.5)
对于大多数语言而言,最后一个算法并不是非常有用,因为要处理任意大小的斐波那契数列,你需要某种无限精度的十进制算术库,虽然它是常数时间,但实际上它可能比简单的对无限精度整数进行对数时间算法操作要慢,至少在
n很大时是这样。