f(n)=f(n-1)+f(n-1)递归时间复杂度

Question

为啥讲f(n)=f(n-1)+f(n-1)这个递归时间复杂度的时候，画出递归树了，就是数节点树来计算O(f(n))。后面的递归算法又是用递归深度*每一次递归时间复杂度来计算。这里就懵逼了。不用统一的方法讲嘛？每个算法都用不同的方法来计算时间复杂度？那还有啥归纳性呢？

Answer 1

liuyubobobo 2018-01-28 12:19:23

因为斐波那契数列的递归算法和归并排序的递归算法，在每一个节点上做的事情，复杂度是有区别的。

对于斐波那契数列的递归算法来说中，每一个节点，不管传入的n是多少，时间复杂度都是O(1)的，所以我们数有多少个节点，时间复杂度就是多少。

对与归并排序来说，每一个节点的输入规模是k的话，在这个节点上的时间复杂度就是O(k)的。所以我们不能简单的数出有多少个节点，然后乘以一个“公共的”每个节点上的时间复杂度。因为每个节点上的时间复杂度不同！但是，每一层的时间复杂度是相同的！都是O(n)，一共有logn层，所以时间复杂度是O(nlogn)的。

至于你说的归纳性，是的，递归算法的时间复杂度分析就是这么复杂。在这个课程中我提到的主定理，就是归纳出的递归问题的时间复杂度计算的公式。他是这个样子的：

它本身就是分情况讨论的。如果有兴趣，可以自行搜索一下主定理，学习一下严谨的递归算法的复杂度计算。

不过一般面试不太会考察这么严谨的复杂度计算，对于一般递归问题的复杂度大概有一个概念就好了。在这里，明白，这二者最大的区别在于，对于斐波那契额数列来说，每个节点的计算量都是一致的；而对于归并排序来说，每个节点的计算量和随着节点在递归树上深度的增加而递减的，所以导致了不同的计算方法。就够了：）