递归求Fibonacci数列的时间复杂度到底是多少?

Ox00 结论

个人认为，严格意义上的时间复杂度应为：

$O((\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n)$

0x01 引言

最近学习数据结构，书中将递归实现的Fibonacci数列的时间复杂度一笔带过，称Fibonacci数列的时间复杂度为O(2^n)，在网上查了查O(2^n)的由来。但在知乎上又看到有人将Fibonacci数列的时间复杂度算出来是$O((\frac{1+\sqrt5}{2})^n)$。这里进行讨论。个人想法，有问题希望大家多多包含，并指出问题所在。

0x02 递归代码

– C代码

#include <stdio.h>

long fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}


int main()
{
    int i;
    for(i=0; i<10; i++)
    {
        printf("%d\n", fib(i));
    }
    return 0;
}
复制代码

– 运行

0x03 时间复杂度

– 说法一 $O(2^n)$

如上图，要想得到 fib(6) 需要先计算 fib(5) 和 fib(4) ; 想要的到 fib(5)需要先计算 fib(4) 和 fib(3) ；以此类推。将红色框内的 fib(2) 和 fib(1) 移动到上一次最右侧，则上一层共 $2^3 = 2^{n-3} = 8$ 。这样作为计算，很容易得到时间复杂度为 $O(2^n)$。

– 说法二 $O((\frac{1+\sqrt5}{2})^n)$

fib(1) 和 fib(2) 的个数并不能直接用 $2^{n-2}$ 进行粗略的计算。记 fib(6) 为第1层，则fib(1) 为第6层，fib(2) 为第5层。显然，fib(1) 和 fib(3) 的个数是相同的。所以 fib(1) 和 fib(2) 的总个数为 fib(4)+fib(5)=3+5=8 。而又 fib(4)+fib(5)=fib(6)=fib(n) ，所以 fib(1) 和 fib(2) 的总个数为fib(n) 。根据斐波那契数列的通项公式得出:

$fib(n)=\frac{1}{\sqrt5}((\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n)$
通过求同阶方程，最终得出时间复杂度为 $O((\frac{1+\sqrt5}{2})^n)$。

– 分析（求解）

• f(n)

  fib(n) 的语句频度等于递归过程中fib(1)和fib(2)总的执行次数。

  所以，求解递归算法的时间复杂度相当于递归方程求解。

  对于斐波那契数列

  当n>=2时 有 f(n)=f(n-1)+f(n-2)

  当n=0或n=1 有 f(n)=1

  递归方程求解，也就是求斐波那契数列的通项公式。

      $f(n)=\frac{1}{\sqrt5}((\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n)$

• "O"

  求与Fn同阶的函数。算法中同阶指的是，当 n->∞ 时，两个函数之比的结果是一个非0的常数，则称这两个函数是同阶的。

  • 如果时间复杂度是$O(2^n)$。相比求极限，结果为0

  • 如果时间复杂度是$O((\frac{1+\sqrt5}{2})^n)$。相比求极限，结果为$\frac{1}{\sqrt5}$

• ret: 斐波那契数列的通向公式函数与$(\frac{1+\sqrt5}{2})^n$是同阶的。

– 另一种思路

设fib(n)的执行时间为T(n)， 则 fib(n-1) 的执行时间为 T(n-1)，fib(n-2) 的执行时间为 T(n-2)。语句 if(n==0 || n==1) return 1; 的执行时间为O(1)。if 判断语句相对于 return 语句的时间可以忽略。

所以$T(n)=T(n-1)+T(n-2)$。

当n=1或n=2时，fib函数执行return 1，执行时间为$O(1)$。

综上：