请帮助我逐步找出以下算法的时间复杂度（我需要逐步解释，因为我知道最终答案）
int fun1（int n）{
if (n <= 1) return n;
return 2*fun1(n-1);
}
int fun2（int n）{
if (n <= 1) return n;
return fun2(n-1) + fun2(n-1);
}
对于func1，假设我们从n开始。
很明显func1(n)在其内部调用func(n-1)，func (n-1)调用func(n-2)，func(n-2)调用func(n-3) ...依此类推，直到调用func(1)并返回1都会中断递归循环。这意味着对于给定的n次，我们调用函数n次，您可以使用小n进行计数和验证。
简而言之func1（n）-> func1（n-1）.... func（1）[总调用次数= n]
由于没有的操作数[此处没有函数调用]随n [这里等于n]线性增加。
我们具有func1时间复杂度为
复杂度：O(n)
现在的问题是2*func1(n-1)与func2(n-1) + func2(n-1)不同，这是严格的否定！因为在前者中，我们仅调用一次函数，但在后者中，我们调用了函数twice。
让我进一步解释一下：
[func2(n)->执行（func2(n-1) + func2(n-1)）现在func2(n-1)->执行（func2(n-2) + func2(n-2)）...等。如您所见，每个函数调用两次调用该函数，而不是更早调用一次，因此我们的时间复杂度为func2为：
复杂度：O( 2^n - 1 )
现在如何得出这个数字：
func2(n)正在呼叫func2(n-1) two次。func2(n-1)也两次调用func2（n-2）因此调用func2(n)一次调用func2(n-2)2*2= 4次，类似地，一直func2(n-3)2*2*2= 8次，一直到被称为func2(1)次的2^(n-1)。
因此总数函数调用的数量为=no. of times func2(n)+no. of times func2(n-1)+no. of times func2(n-2).... no. of times func2(1)。
因此，总通话次数为：
Total Calls = 1 + 2 + 2*2 ... + 2^(n-1)。
Total Calls = (2^n - 1)/(2-1)->这是Geometric Progression之和的公式。
因此
[Total Calls = 2^n - 1或func2的复杂度是：
复杂度= O( 2^n - 1 )。
这里2 ^ n代表2等于幂n，例如2 ^ 2 = 4，2 ^ 3 = 8、2 ^ 4 = 16、2 ^ n = 2 * 2 * 2 ...（n次）。