下面函数执行的时间复杂度是多少？( )
static int fib(int n) {
if (n <= 2)
return 1;
else
return fib(n-1) + fib(n-2)
}O(2^n)
O(1)
O(2^n-1) + O(2^n-2)
这是台阶问题的实现逻辑，
一个子问题时间 = F(n-1)+ F(n-2)，也就是一个加法的操作，所以复杂度是 O(1)；
问题个数 = 递归树节点的总数，递归树的总节点 = 2^n-1， 所以是复杂度O(2^n)。
所以递归实现方式的时间复杂度 = O(1) * O(2^n) = O(2^n)，指数级别的，存在性能问题。
一个子问题时间 = F(n-1)+ F(n-2)，也就是一个加法的操作，所以复杂度是 O(1)；
问题个数 = 递归树节点的总数，递归树的总节点 = 2^n-1， 所以是复杂度O(2^n)。
所以递归实现方式的时间复杂度 = O(1) * O(2^n) = O(2^n)，指数级别的，存在性能问题。
