指数级计算复杂度 调用Fibonacci函数次数
指数级计算复杂度
计算调用次数
#include <stdio.h>
long fibonacciCallTimes(long n); int main(void) {
long result,start,end,number;
int i; printf("Enter an integer-SATRT:");
scanf("%ld",&start);
printf("Enter an integer-END:");
scanf("%ld",&end); for (i=start; i<=end; i++) {
number = i;
result=fibonacciCallTimes(number);
printf("fibonacciCallTimes(%ld)=%ld\n",number,result);
} return 0;
} long fibonacciCallTimes(long n) {
/* base case */
if(n==0 || n==1) {
return 1;
} else {
return 1+fibonacciCallTimes(n-1)+fibonacciCallTimes(n-2);
}
}
Enter an integer-SATRT:0
Enter an integer-END:11
fibonacciCallTimes(0)=1
fibonacciCallTimes(1)=1
fibonacciCallTimes(2)=3
fibonacciCallTimes(3)=5
fibonacciCallTimes(4)=9
fibonacciCallTimes(5)=15
fibonacciCallTimes(6)=25
fibonacciCallTimes(7)=41
fibonacciCallTimes(8)=67
fibonacciCallTimes(9)=109
fibonacciCallTimes(10)=177
fibonacciCallTimes(11)=287
请按任意键继续. . .
分析上边逻辑漏洞
正确答案:
为了计算第n个Fibonacci数,共需要调用fibonacci函数的此时达到2^n数量级。
Enter an integer-SATRT:0
Enter an integer-END:31
Fibonacci(0)=0
Fibonacci(1)=1
Fibonacci(2)=1
Fibonacci(3)=2
Fibonacci(4)=3
Fibonacci(5)=5
Fibonacci(6)=8
Fibonacci(7)=13
Fibonacci(8)=21
Fibonacci(9)=34
Fibonacci(10)=55
Fibonacci(11)=89
Fibonacci(12)=144
Fibonacci(13)=233
Fibonacci(14)=377
Fibonacci(15)=610
Fibonacci(16)=987
Fibonacci(17)=1597
Fibonacci(18)=2584
Fibonacci(19)=4181
Fibonacci(20)=6765
Fibonacci(21)=10946
Fibonacci(22)=17711
Fibonacci(23)=28657
Fibonacci(24)=46368
Fibonacci(25)=75025
Fibonacci(26)=121393
Fibonacci(27)=196418
Fibonacci(28)=317811
Fibonacci(29)=514229
Fibonacci(30)=832040
Fibonacci(31)=1346269
请按任意键继续. . .
最新文章
- 【Android】Android ObjectAnimator动画初识、模仿
- Extjs的数据读取器store和后台返回类型简单解析
- 系统启动时,spring配置文件解析失败,报”cvc-elt.1: 找不到元素 &#39;beans&#39; 的声明“异常
- Python 定制类与其对象的创建和应用
- 微软职位内部推荐-Senior Development Lead
- Android开发之极光推送基本步骤
- Qt Painter放大时,event处理应该注意的要点
- OD调试9—实例:深入分析代码完成软件破解
- json解析的函数eval_r() 和 JSON.parse()
- iOS MVVM 参考
- 项目架构开发:数据访问层之UnitOfWork
- 将Excle中的数据批量导入数据库
- 【Unity Shader实战】卡通风格的Shader(一)
- 存储那些事儿(一):异构虚拟化一种实现SMIS
- 图片像素对比OpenCV实现,实现人工分割跟算法分割图像结果的对比
- Kafka系列2-producer和consumer报错
- semantic-ui 下拉框
- Nginx 决策浏览器缓存是否有效
- C# BackgroundWorker使用总结
- openshift 容器云从入门到崩溃之六《Source-to-Image》