数据结构常见算法原理讲解100篇(一)-递归和分治算法原理及案例应用

举报
格图洛书 发表于 2021/11/19 01:04:28 2021/11/19
【摘要】 前言 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 01.递归 每谈到递归,我们总会免不了联系到斐波那契(Fibonacci)数列,当然也不可忽视,斐波那契...

前言

在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

01.递归

每谈到递归,我们总会免不了联系到斐波那契(Fibonacci)数列,当然也不可忽视,斐波那契数列确实是一个很好的例子。但在现实当中,我们只有在迫不得已的情况下才使用递归,因为递归本身的效率并不理想,但他的思想却值得我们留存在记忆之中。

题目一:斐波那契数列

写一个函数,输入n,求斐波那契数列的第n项。

我们先一起看一下该题目的递归实现,从而学会写递归的三要素:


  
  1. //第一要素:明确你这个函数想要干什么
  2. //函数功能:计算斐波那契数列的第n项
  3. long long Fibonacci(unsigned int n)
  4. {
  5.     //第二要素:寻找递归结束条件
  6.     if( n <= 1)
  7.         return i == 0 ? 0 : 1;
  8.     //第三要素:找出函数的等价关系式
  9.     return Fibonacci(n - 1) + Fibonacci(n - 2);
  10. }

但在面试的时候,面试官可不会轻易放过你,他会觉着上面的递归实现效率太低,原因在于我们在求斐波那契数列第n项的时候,中间计算了很多重复项,而且是不必要的计算,如下图的递归树:

文章来源: wenyusuran.blog.csdn.net,作者:文宇肃然,版权归原作者所有,如需转载,请联系作者。

原文链接:wenyusuran.blog.csdn.net/article/details/108374962

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。