带你逐步分析递归算法的时间复杂度 很多同学对递归算法的时间复杂度都不甚了解。 同一道题目，同样使用递归算法，有的同学写出了O(n)的代码，有的同学就写出了O(logn)的代码 这是为什么呢， 就是因为对递归的时间复杂度理解的不够深入导致的 如果恰巧正在读本文的你也对递归算法的时间复杂度懵懵懂懂，请认真读完本篇文章，一定会有所收获。我这里也整理出一份PDF，pdf中不仅有刷题大纲、刷题顺序，还有详细图解，每一本pdf发布之后都广受好评先，PDF中攻击20w字详细图解了 100多道力扣上的经典题目，上图：
无论现在要不要学习算法，先去下载吧，你会发现详见很晚！BAT程序员的算法学习手册PDF开放下载！ 我先通过一道简单的面试题，来带大家逐步分析递归算法的时间复杂度，最后找出最优解。 来看一下这道面试题：求x的n次方 大家想一下这么简单的一道题目 代码应该如何写。 最直观的方式应该就是，一个for循环求出结果，代码如下 时间复杂度为 此时面试官会说，有没有效率更好的算法呢。 如果同学们此时没有思路，建议不要说：我不会，我不知道。可以和面试官探讨一下，问：可不可以给点提示。 面试官一般会提示：考虑一下递归算法 有的同学就写出了如下这样的一个递归的算法，使用递归解决了这个问题 面试官问：那么这份代码的时间复杂度是多少？ 有的同学可能一看到递归就想到了，其实并不是这样 递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数 那我们再来看代码，我们递归了几次呢。 每次n-1，递归了n次 时间复杂度是，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项 所以这份代码的时间复杂度是 这个时间复杂度可能就没有达到面试官的预期。 于是同学又写出了这样的一个递归的算法的代码如下 ，来求 x的n次方 面试官看到后微微一笑，问这份代码的时间复杂度又是多少呢？ 我们来分析一下 首先看递归了多少次呢，可以把递归的次数 抽象出一颗满二叉树。 我们刚刚写的这个算法，可以用一颗满二叉树来表示（为了方便表示 我选择n为偶数），如图： 
当前这颗二叉树就是求x的n次方，n为16的情况 n为16的时候 我们进行了多少次乘法运算呢 这棵树上每一个节点就代表着一次递归并进行了一次相乘操作 所以 进行了多少次递归的话，就是看这棵树上有多少个节点。 熟悉二叉树的同学应该知道如何求满二叉树节点数量 这颗满二叉树的节点数量就是 有同学就会发现 这其实是等比数列的求和公式， 如果不理解的同学可以直接记下来这个结论。 这个结论在二叉树相关的面试题里也经常出现。 这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示 
时间复杂度忽略掉常数项之后，我们发现这个递归算法的时间复杂度依然是O(n)。 此时面试官就会问， 貌似这个递归的算法依然还是啊， 很明显没有达到面试官的预期 那么在思考一下 的递归算法应该怎么写 这里在提示一下 上面刚刚给出的那份递归算法的代码，是不是有哪里比较冗余呢。 来看这份优化后的递归算法代码 那我们看一下 时间复杂度是多少 依然还是看他递归了多少次 我们可以看到 这里仅仅有一个递归调用，且每次都是 n/2 所以这里我们一共调用了 log以2为底n的对数次 每次递归了做都是一次乘法操作，这也是一个常数项的操作， 所以说这个递归算法的时间复杂度才是真正的O(logn)。 如果同学们最后写出了这样的代码并且时间复杂度分析的非常清晰，相信面试官是比较满意的。 最后希望通过这么一个简单的面试题，让大家真正了解了递归算法的时间复杂度该如何分析。 最后无论是学生还是工作多年的老鸟，都需要学习算法知识，算法学好了，进大厂还是很容易的，对以后的事业发展很有帮助，我已经把详细的算法学习路线都整理出来，并开源在Github上， 上图：
这个项目里面有200道经典算法题目刷题顺序、配有60w字的详细图解，常用算法模板总结，以及难点视频讲解，按照list一道一道刷就可以了！ 去看看吧，这个Github算法学习项目会惊艳到你！youngyangyang04/leetcode-master Hello，我是Carl，哈工大师兄，获得过ACM亚洲区奖牌，先后在BAT中的两家采坑，一位文舞双全的程序员。交流可以加我:Carl的个人 码字不已，希望对你有所帮助！ @代码随想录 点个赞就是对我最大的鼓励，笔芯~
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/80079.html
