首页 > 代码库 > 时间复杂度O(n),空间复杂度O(1)解斐波那契数列

时间复杂度O(n),空间复杂度O(1)解斐波那契数列

#include <stdio.h>#include <iostream>using namespace std;long long fibs1(int in_iN) {    if(in_iN < 0) {        return -1;    }else if(in_iN == 0) {        return 0;    }else if(in_iN == 1) {        return 1;    }    long long t_i1 = 0;    long long t_i2 = 1;    long long t_iValue = http://www.mamicode.com/0;    int t_k = 2;    while(t_k <= in_iN) {        t_iValue = t_i1 + t_i2;        t_i1 = t_i2;        t_i2 = t_iValue;        t_k ++;    }    return t_iValue;}long long fibs2(int in_iN) {    if(in_iN < 0) {        return -1;    }else if(in_iN == 0) {        return 0;    }else if(in_iN == 1) {        return 1;    }else {        return fibs2(in_iN - 1) + fibs2(in_iN - 2);    }}int main(){    int    in_iN = 40;    cout << fibs1(in_iN) << endl;    cout << fibs2(in_iN) << endl;    cin >> in_iN;    return 0;}

 

时间复杂度O(n),空间复杂度O(1)解斐波那契数列