数据结构常见算法原理讲解100篇(一)-递归和分治算法原理及案例应用
【摘要】
前言
在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
01.递归
每谈到递归,我们总会免不了联系到斐波那契(Fibonacci)数列,当然也不可忽视,斐波那契...
前言
在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
01.递归
每谈到递归,我们总会免不了联系到斐波那契(Fibonacci)数列,当然也不可忽视,斐波那契数列确实是一个很好的例子。但在现实当中,我们只有在迫不得已的情况下才使用递归,因为递归本身的效率并不理想,但他的思想却值得我们留存在记忆之中。
题目一:斐波那契数列
写一个函数,输入n,求斐波那契数列的第n项。
我们先一起看一下该题目的递归实现,从而学会写递归的三要素:
-
//第一要素:明确你这个函数想要干什么
-
//函数功能:计算斐波那契数列的第n项
-
long long Fibonacci(unsigned int n)
-
{
-
//第二要素:寻找递归结束条件
-
if( n <= 1)
-
return i == 0 ? 0 : 1;
-
//第三要素:找出函数的等价关系式
-
return Fibonacci(n - 1) + Fibonacci(n - 2);
-
}
但在面试的时候,面试官可不会轻易放过你,他会觉着上面的递归实现效率太低,原因在于我们在求斐波那契数列第n项的时候,中间计算了很多重复项,而且是不必要的计算,如下图的递归树:
文章来源: wenyusuran.blog.csdn.net,作者:文宇肃然,版权归原作者所有,如需转载,请联系作者。
原文链接:wenyusuran.blog.csdn.net/article/details/108374962
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)