可能对递归理解的还不够!
递归算法来说,代码一般都比较简短,从算法逻辑上看,所用的存储空间也非常少,但运行时需要内存可不见得会少。 时间复杂度分析来看看这个求斐波那契的递归算法的时间复杂度是多少呢? 在讲解递归时间复杂度的时候,我们提到了递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。 可以看出上面的代码每次递归都是O(1)的操作。再来看递归了多少次,这里将i为5作为输入的递归过程 抽象成一颗递归树,如图:中,可以看出f(5)是由f(4)和f(3)相加而来,那么f(4)是由f(3)和f(2)相加而来 以此类推。 在这颗二叉树中每一个节点都是一次递归,那么这棵树有多少个节点呢? 我们之前也有说到,一棵深度(按根节点深度为1)为k的二叉树最多可以有 2^k - 1 个节点。 所以该递归算法的时间复杂度为 O(2^n) ,这个复杂度是非常大的,随着n的增大,耗时是指数上升的。 来做一个实验,大家可以有一个直观的感受。 以下为C++代码,来测一下,让我们输入n的时候,这段递归求斐波那契代码的耗时。这里相当于用first和second来记录当前相加的两个数值,此时就不用两次递归了。 因为每次递归的时候n减1,即只是递归了n次,所以时间复杂度是 O(n)。 同理递归的深度依然是n,每次递归所需的空间也是常数,所以空间复杂度依然是O(n)。 代码(版本二)的复杂度如下:
此时再来测一下耗时情况验证一下: (编辑:甘孜站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |