数据结构算法每日一练（一）斐波那契数列

题目：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0,

F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

（1）请按照上面的定义用递归的方式求第n向Fibonacci数列的值: int fibonacci(int n);

（2）给出此递归函数的时间复杂度。

（1）

#include <iostream>
using namespace std;
int fibonacci (int n){
    if (n == 1 || n == 2)
        return 1;
    else return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
    int n ;
    cin >> n;
    int res = fibonacci (n);
    cout << res << endl;
    return 0;
}

（2）

递归结构图如下：

1、时间复杂度为(二叉树的节点个数）：

因为递归后不属于完全二叉树，因此结点小于$(2^h)-1$，近似归为$(2^h)$

时间复杂度近似为 $(2^h)-1= O(2^n)$

更精确一些时间复杂度为$O(F(n))$

$F(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n]$

$O(F(n)) = O((\frac{1+\sqrt{5}}{2})^n)$

2、空间复杂度为(树的高度)：h = $O(n)$.

二叉树的高度h根据具体数据推算为 n - 1

递归算法时间复杂度过大，优化算法，采取递推算法即动态规划

#include <iostream>
using namespace std;
int fibonacci(int n)
{
    int  fib[101];			//采用数组保存中间结果
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    return fib[n];
}
int main() {
    int n ;
    cin >> n;
    int res = fibonacci (n);
    cout << res << endl;
    return 0;
}

时间复杂度为：$O(n)$

空间复杂度为： $O(1)$.