首先，以下是主要代码
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次主要运算，根据指数乘以时间复杂性的定义，每次我们增加输入变量，运算的次数都应该增加一倍，我认为这里不是这样的情况.
对于朴素的斐波纳契实现，我们确实发现了指数时间复杂性(或者更准确地说是O(2^n))，最明显的是通过查看函数调用的树图.
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).
定义指数乘以时间复杂度，每增加一次输入变量，运算次数就应该翻一番
时间复杂度为O(n)，时间复杂度为O(n).如果是b=2的话每次只会翻倍.然而，你可以有b=3(每次三倍)，b=4(四倍)或b=1.2213，你得到的点.
我们还可以编写代码来为我们计数:
var counter = 0;
function fib(n){
counter++;
if( n <= 1 ){
return 1;
}
return fib(n-1) + fib(n-2);
}
for( var i = 0; i < 15; ++i ){
counter = 0;
fib(i);
console.log("Fib evaluations for " + i + ": " + counter);
}
如果对计数器进行对数绘制，则会得到以下图片，证实了执行时间的指数增长:
