算法学习之斐波那契数列

什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。 —— 以上来自百度百科

斐波那契数列代码实现

// 时间复杂度：O2^n
int fib(int n) {
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return fib(n - 1) + fib(n - 2);
}

int main() {
    int n = 10;
    time_t startTime = clock();
    int res = fib(n);
    time_t endTime = clock();

    cout<<"fib("<<n<<") = "<<res<<endl;
    cout<<"time : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;

    return 0;
}

斐波那契数列代码优化

vector<int> memo;
int num = 0;

// 记忆化搜素
// 算法复杂度：ON
int fib(int n) {

    num++;

    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    if (memo[n] == -1)
        memo[n] = fib(n - 1) + fib(n - 2);

    return memo[n];
}

int main() {

    num = 0;

    int n = 1000;
    memo = vector<int>(n + 1, -1);

    time_t startTime = clock();
    int res = fib(n);
    time_t endTime = clock();

    cout<<"fib("<<n<<") = "<<res<<endl;
    cout<<"time : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
    cout<<"run function fib() "<<num<<" times"<<endl;

    return 0;
}

斐波那契数列之动态规划法

// 动态规划
int fib2(int n) {
    vector<int> memo2(n + 1, -1);

    memo2[0] = 0;
    memo2[1] = 1;
    for (int i = 2; i <=n ; ++i) {
        memo2[i] = memo2[i - 1] + memo2[i - 2];
    }

    return memo2[n];
}

int main() {

    num = 0;

    int n = 40;
    memo = vector<int>(n + 1, -1);

    time_t startTime = clock();
    int res = fib2(n);
    time_t endTime = clock();

    cout<<"fib("<<n<<") = "<<res<<endl;
    cout<<"time : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
    cout<<"run function fib() "<<num<<" times"<<endl;

    return 0;
}