我无法理解指数时间复杂度

Question

首先，这是主要代码

var fib = function(n) {
if (n===0) return 0
if (n===2 || n===1) return 1
return fib(n-1) + fib(n-2)
};   

所以问题是打印斐波那契数，现在放开问题的逻辑，我可以看到，每当我们将变量 n 加 1 时，该函数就会被调用 2 * n 次，所以即使当我们考虑通过返回变量来回溯函数，这将是 4 * n 主要操作，并且根据指数倍时间复杂度的定义，每次我们增加输入变量，操作次数应该增加一倍，我认为不是案例在这里。

我是DSA新手，所以如果我错了，请纠正我，任何帮助将不胜感激

Answer 1

对于简单的斐波那契实现，我们确实发现了指数时间复杂度，通过查看函数调用的树形图最容易看出。

        F_5
   /          \
  F_3         F_4
/    \      /    \
F_1  F_2   F_3   F_2
          /   \
        F_2   F_1

您可以清楚地看到每行的执行次数如何翻倍（1,2,4,...）

为了说服自己，如果需要，请画出

F_6

和

F_7

的图表。