algorithm - 为什么递归计算斐波那契数列的时间复杂度是2^n而不是2^n^2？

Question

我发现这是一个很好的例子，可以理解递归调用函数的运行时间。这里有一个很好的问题概述:https://stackoverflow.com/a/33663627/9750088

但是，我的误解来自将 2^1 + 2^2.... 2^n-1 求和为递归树调用的每个级别的总和。对我来说，这个 1+2...n-1 的总和似乎是 n(n-1)/2，在我看来直觉上它就像大 O 表示法中的 n^2，因此导致总运行时间为 O 2 ^n^2 大 ) 符号。树叶的总和究竟是如何变成 2^n 的？

Answer 1

我对该链接中答案的理解:

1. 首先，您应该了解该递归树中有多少个节点。对于数字 n，树中有 2^(n-1) 个叶子，并且 2^(n-1)-1非叶节点。(对于根级别，有2^0个节点；第二级:2^1个节点；...最后一个非叶级别-the第二低层:2^(n-2) 个节点。总和为 2^0+2^1+...+2^(n-2)=2^(n -1)-1.这个很重要，你可以试着找个例子弄明白。)。所以总共有2^(n-1)+2^(n-1)-1个节点。
2. 那么时间复杂度是 O(2^(n-1)+2^(n-1)-1)->O(2^(n-1)+2^(n-1) )->O(2*2^(n-1))->O(2^n)