当前位置:首页 / 文章测试 / C++斐波那契的时间复杂度

C++斐波那契的时间复杂度

开始打字练习

#include <iostream>

#include <cstring>

using namespace std;

int cnt = 0;

int f1(int n) {

cnt++;

if (n<3) return 1;

return f1(n-1) + f1(n-2);

}

int a[100];

int f2(int n) {

cnt++;

if (n<3) return 1;

if (a[n]) return a[n];

return a[n] = f2(n-1) + f2(n-2);

}

int f3(const int n) {

int b[n+1];

memset(b, 0, sizeof(b));

b[1] = b[2] = 1;

for(int i=3; i<=n; i++) {

cnt++;

b[i] = b[i-1] + b[i-2];

}

return b[n];

}

int main() {

int n = 30;

cout << f1(n) << endl;

cout << "f1 cnt=" << cnt << endl;

cnt = 0;

cout << f2(n) << endl;

cout << "f2 cnt=" << cnt << endl;

cnt = 0;

cout << f3(n) << endl;

cout << "f3 cnt=" << cnt << endl;

return 0;

}

声明:以上文章均为用户自行发布,仅供打字交流使用,不代表本站观点,本站不承担任何法律责任,特此声明!如果有侵犯到您的权利,请及时联系我们删除。