网站运营者网址,做网站一般多钱,wordpress 页面 背景图,wordpress改网站信息王有志#xff0c;一个分享硬核Java技术的互金摸鱼侠加入Java人的提桶跑路群#xff1a;共同富裕的Java人 今天我们将会分析上篇文章中递归算法存在的问题#xff0c;并通过迭代去优化。
递归存在的问题
上一篇中#xff0c;我们计算了序号10以内的斐波那契数。今天为了清… 王有志一个分享硬核Java技术的互金摸鱼侠加入Java人的提桶跑路群共同富裕的Java人 今天我们将会分析上篇文章中递归算法存在的问题并通过迭代去优化。
递归存在的问题
上一篇中我们计算了序号10以内的斐波那契数。今天为了清晰的展示递归解法存在的问题我们试着计算序号为50的斐波那契数如果电脑的性能较差的话就不要尝试了。可以看到从计算F(40)开始递归解法的耗时如同“坐火箭”般上升这种情况是我们无法忍受的。在上一篇文章中我们有一个练习就是优化递归求解第n个斐波那契数。那么今天我们就一起看看通过递归求解问题出现在哪里通过之前构建的F(6)的递归树我们可以看到递归求解斐波那契数时存在大量重复的计算例如仅仅是计算F(2)就出现了5次。那么比较容易想到的优化方案就是缓存计算结果使用时再取出。因此我们引入缓存减少重复计算提升执行速度和复杂度分析中的空间换时间呼应上了。我们来看下具体实现
private static long fib_recursion_memory(int n) {
return fib_recursion_memory(n, new long[n 1]);
}private static long fib_recursion_memory(int n, long[] memory) {if (n 2) {return n;}if (memory[n] ! 0) {return memory[n];}memory[n] fib_recursion_memory(n - 1, memory) fib_recursion_memory(n - 2, memory);return memory[n];
}代码并不复杂通过引入long类型数组记录已经计算过的斐波那契数以达到减少重复计算的目的。除此之外还有没有其他方法求解第n个斐波那契数
迭代
我们在使用递归时通常是将规模较大的问题拆分为规模较小的问题依次求解组合的过程。反之我们也可以从最小规模的问题开始逐步累积到规模较大的问题。迭代正是这样一种方法。迭代是数学概念引入编程中的非常容易与循环混淆。来看下百度百科中的定义 迭代是重复反馈过程的活动其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”而每一次迭代得到的结果会作为下一次迭代的初始值。 既然说到非常容易与循环混淆那么再来看看循环的定义 循环是程序设计语言中反复执行某些代码的一种计算机处理过程常见的有按照次数循环和按照条件循环。 通过定义我们很容易看出迭代与循环的差别循环只是程序的重复执行对计算结果没有要求而迭代需要将每次计算结果应用到下一次循环中所以可以说迭代只循环的子集。
迭代求解第n个斐波那契数
事实上递归都是可以改写为迭代的形式不那么优雅而且邓俊峰老师也在《数据结构》中说到 实际上属于尾递归形式的算法均可以简捷地转换为等效的迭代版本。 这给了我们使用迭代改写递归求解斐波那契数列的理论基础下面我们直接开始。首先斐波那契数列的的递推公式是从第3项开始因此我们需要处理第12项的特殊情况代码如下
if(n 0) {return 0
}if(n 3) {return 1;
}根据递推公式如果计算n的值我们需要知道 n−1 和 n−2 的值那么我们声明3个变量用p代表 n−2 用q代表 n−1 用result代表n那么p设置为 F(1) q设置为 F(2) result设置为 F(3) 代码如下
int p 1, q 1, result p q;现在我们已经有了3个变量表示 F(1) 到 F(3) 仅仅是这些你已经可以计算出F(4)的值了
p q;
q result;
result p q;如果想要计算 F(n) 的值我们只需要不断的重复计算 F(4) 的过程即可
for(int i 4; i n; i) {p q;q result;result p q;
}完整的代码如下
private static int fib(int n) {
if(n 0) {return 0;
}if (n 3) {return 1;
}int p 1, q 1, result p q;
for (int i 4; i n; i) {p q;q result;result p q;
}
return result;
}随着循环的进行每次计算的结果都会带入到下一次的循环这就是定义中所指的每次迭代结果作为下一次迭代的初始值进行处理。至于通过迭代求解的斐波那契数列的时间复杂度相信大家一眼就可以看出来了吧如果你了解动态规划的话你很容易就能想到迭代求解斐波那契数列就是简单的动态规划解法不过这是后话现在我们按下不表。
结语
今天的内容到这里就结束了我们来回顾下都聊了哪些内容首先是回顾了递归求解斐波那契数列的问题通过“记忆”优化了递归的执行速度但是增加了空间复杂度。然后为了更高效我们引入了迭代虽然我并不鼓励大家记忆概念和定义但是你要明白相似概念的区别。最后我们通过迭代的方式求解斐波那契数列实现了 O(n) 复杂度。当然斐波那契数列还有 O ( log _ n ) O(\log\_{}{n}) O(log_n) 的解法不过这不是我们今天的内容。
练习
我们来做几道简单的题目
剑指Offer 10-I 斐波那契数列53.最大子数组和70.爬楼梯121.买卖股票的最佳时机
如果最第53题和121题没有解出来也并没有关系这里涉及到动态规划的知识还没有接触到的小伙伴也不要着急后面是有动态规划的专题的。 如果本文对你有帮助的话还请多多点赞支持。如果文章中出现任何错误还请批评指正。最后欢迎大家关注分享硬核Java技术的金融摸鱼侠王有志我们下次再见
