【王道思维扩展1】求解斐波那契数列的递归和非递归算法 并分析两种时间复杂度

1、斐波那契数列

2、递归与非递归的实现

1）、递归

时间复杂度O(2^N)

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>//环境VS//递归 时间复杂度O(2^N)int count = 0;int Fib(int n){if (n == 3)count++;if (n == 0 || n == 1)return 1;else return Fib(n - 1) + Fib(n - 2);}int main(){int n;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);printf("%d\n", count);//查看n==3被重复计算的次数}

缺点：调用过程计算重复，效率低

优点：代码简单

2）非递归的两种写法

//数组简单的动态规划

时间复杂度O(N) 空间复杂度O(N)

//时间复杂度O(N) 空间复杂度O(N)//简单的动态规划int Fib(int n)//只有一个函数调用,不形成栈帧{int a[1024];a[1] = 1;a[2] = 1;for (int i = 3; i <= n; i++){a[i] = a[i - 1] + a[i - 2]; }return a[n];}

//迭代原理

时间复杂度O(N) 空间复杂度O(1)

//非递归 时间O(N) 空间O(1)//迭代原理int Fib(int n){int result;int per_result;int older_result;per_result = result = 1;while (n > 1){n -= 1;older_result = per_result;per_result = result;result = per_result + older_result;}return result;}