分析递归函数的时间复杂度

递归算法的时间复杂度表达式：

O(T) = R * O(s)

O(T)表示时间复杂度

R表示递归调用的次数

O(s)每次递归调用计算的时间复杂度

想想斐波那契函数，它的递归关系是f(n) = f(n-1) + f(n-2)；乍一看，我们会发现，在斐波那契函数执行期间来计算递归调用的次数似乎并不那么的容易。

解释：这种情况下，我们最好是可以借助执行树，它是一颗被用来表示递归函数执行流程的数。树中的每一个节点代表递归函数的一次调用。所以，树中节点的总数与执行期间递归调用的数量相对应。

递归函数的执行树将形成一个n叉树，这个n就是递归在递归关系中出现的 次数。 还拿斐波那契函数来说事，那它会形成一个二叉树。具体可参考下图。

在深度为n的完全二叉树中，所有节点的数量可以达到2n-1。那么在递归函数f(n)的递归次数的上界也就是2n-1。所以，我们可以估算出f(n)的时间复杂度就是O(2n)

备忘录

备忘录技术是用来优化递归算法时间复杂度的技术。通过缓存和重用中间结果的方式，备忘录可以极大地减少递归调用的次数，也就是减少执行树中分枝的数量。所以，当我们使用备忘录来分析递归算法的时间复杂度时候应该把这减少的部分考虑到。

再把斐波那契函数拎出来说事。通过备忘录技术，我们会对每一个下标n进行斐波那契数进行保存操作。我们也能够确信的是每一个斐波那契数的计算也仅仅出现一次。众所周知的是根据递归关系，一个斐波那契数f(n)依赖于所有n-1在前的斐波那契数。结果就是，计算f(n)递归将调用n-1次，以计算它所依赖的所有先前的数。

现在我们就可以利用文章开头列出的公式来计算备忘录技术应用后的时间复杂度：O(1)n=O(n)。

结论

备忘录不仅优化算法的时间复杂度，而且还可以简化时间复杂度的计算。

希望能给大家带来一定的帮助，欢迎一键三连，谢谢。 

文章来源: laoshifu.blog.csdn.net，作者：红目香薰，版权归原作者所有，如需转载，请联系作者。

原文链接：laoshifu.blog.csdn.net/article/details/122647474