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 节点；...最后一个非叶子级别 -第二低层: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)