recursion - 为什么递归斐波那契的时间复杂度是 O(2^n) 而不是 O(n*2^n)？

Question

我知道递归树中有 O(2^n) 叶子，但是树下的每条路径都需要 O(n) 时间来计算。那么时间复杂度不应该是O（n * 2 ^ n）吗？

标签： recursiontime-complexityfibonacci

Answer 1

在本网站中解释了时间复杂度：here

如果数学解释还不够，考虑用递归树选项构建一个向量，你会得到一个包含 2^n 个元素的向量，所以迭代它的复杂度是 2^n，因为你迭代所有树一次而不是 N 次所有的树。