为什么递归计算斐波那契数列的时间复杂度是2^n而不是2^n^2？
Why is the time complexity of the recursion method for computing the Fibonacci series is 2^n but not 2^n^2?
我发现这是一个很好的例子，可以帮助理解递归调用函数的运行时间。这里有一个很好的问题概述：
但是，我的误解来自将 2^1 + 2^2.... 2^n-1 求和为递归树的每一层调用的总和。对我来说，这个 1+2...n-1 的总和似乎是 n(n-1)/2，在我看来直觉上它就像大 O 表示法中的 n^2，因此导致总运行时间为 O 2 ^n^2 大 ) 符号。树叶的总和究竟是如何变成 2^n 的？
我对那个答案的理解 link:
- 首先你应该了解该递归树中有多少个节点。对于数
n，树中有2^(n-1)个叶子节点，2^(n-1)-1个非叶子节点。（对于根级，有2^0个节点；第二级： 2^1个节点；...最后一个非叶层级-倒数第二层：2^(n-2)个节点。总和是2^0+2^1+...+2^(n-2)=2^(n-1)-1个。这很重要，你可以试着找一些例子和图出来。） 。所以总共有2^(n-1)+2^(n-1)-1个节点。
- 那么时间复杂度是
O(2^(n-1)+2^(n-1)-1)->O(2^(n-1)+2^(n-1))->O(2*2^(n-1))->O(2^n)
我发现这是一个很好的例子，可以帮助理解递归调用函数的运行时间。这里有一个很好的问题概述：
但是，我的误解来自将 2^1 + 2^2.... 2^n-1 求和为递归树的每一层调用的总和。对我来说，这个 1+2...n-1 的总和似乎是 n(n-1)/2，在我看来直觉上它就像大 O 表示法中的 n^2，因此导致总运行时间为 O 2 ^n^2 大 ) 符号。树叶的总和究竟是如何变成 2^n 的？
我对那个答案的理解 link:
- 首先你应该了解该递归树中有多少个节点。对于数
n，树中有2^(n-1)个叶子节点，2^(n-1)-1个非叶子节点。（对于根级，有2^0个节点；第二级：2^1个节点；...最后一个非叶层级-倒数第二层：2^(n-2)个节点。总和是2^0+2^1+...+2^(n-2)=2^(n-1)-1个。这很重要，你可以试着找一些例子和图出来。） 。所以总共有2^(n-1)+2^(n-1)-1个节点。 - 那么时间复杂度是
O(2^(n-1)+2^(n-1)-1)->O(2^(n-1)+2^(n-1))->O(2*2^(n-1))->O(2^n)