［数据结构与算法分析］斐波那契数列递归算法时间复杂度为多少？

Question

A:O(logN)
B:O(N)
C:O(N!)
D:O(FN)
原题：The Fibonacci number sequence {FN} is defined as: F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, .... The time complexity of the function which calculates FN recursively is:

Answer 1

long fab(long n)
{
    if (n < 2) return 1;
    return fab(n - 1) + fab(n - 2);
}

简单推断一下，当n>2时，递归调用的次数call_fab(n) = 2*fab(n) - 1，再简单证明一下。

用call_fab(n)代表递归调用的次数

n = 3时，调用fab(3)，会递归调用fab(1)和fab(2)，而fab(1)和fab(2)只需要调用一次，加上本身一次，一共调用3次，而fab(3) = 2，3 = 2 * 2 - 1，满足推断

n = 4时，fab(4) = fab(3) + fab(2)，所以call_fab(4) = 1 + call_fab(3) + call_fab(2) = 5

fab(4) = 3，满足5 = 3 * 2 - 1

同理n=5也可以简单计算得出，这样我有连续3个结果，作为归纳法证明的基础

假设n = k（k >= 5）成立，即

fab(k) = fab(k-2) + fab(k - 1)，有call_fab(k) = 2fab(k) - 1

那么当n=k+1时，fab(k+1) = fab(k - 1) + fab(k)，

call_fab(k+1) = 1 + call_fab(k - 1) + call_fab(k) = 1 + 2fab(k-1) - 1 + 2fab(k) - 1

= 2(fab(k-1) + fab(k)) - 1 = 2fab(k+1) - 1，归纳法得证。

所以，对于大于2的整数n，其斐波那契数列递归算法的调用次数为2*n的斐波那契数列值 - 1，故答案是D，时间复杂度和该数列是一致的。

Answer 2

答案应该是2的n次方，当n为3时，调用五次，n为4调用九次

Answer 3

B
附加：当使用{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1，求解释，会将时间复杂度减为A