聊聊斐波那契数列中递归的重复计算

发布时间:2017-7-9 7:35:15编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"聊聊斐波那契数列中递归的重复计算 ",主要涉及到聊聊斐波那契数列中递归的重复计算 方面的内容,对于聊聊斐波那契数列中递归的重复计算 感兴趣的同学可以参考一下。

public int fibonacci(int n) {    if (n < 2) {return 0;}    if (2 == n) {return 1;}    return fibonacci(n - 1) + fibonacci(n - 2);}

但是,这个函数去执行的时候,会发现非常的慢。那是什么原因呢?
我们仔细观察一下,每一次递归的时候,我们都会调用两个,所以,计算时,从n、n-1、… 0会是一个金字塔,二叉树的分布,也就是靠近0的底层,会有2^n次运算,就是一个指数级运算,计算时间复杂度为O(2^n),运算速度是非常慢的。
原因是什么呢?假如,我们计算的是10,那么它相应的要计算 9 + 8,而9要计算 8 + 7, 8又要计算 7 + 6.相当于越往底层去,计算的次数越多。



上一篇:HTML基础知识总结

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款