如何计算递归算法的时间复杂度？
int pow1(int x,int n) {
if(n==0){
return 1;
}
else{
return x * pow1(x, n-1);
}
}
int pow2(int x,int n) {
if(n==0){
return 1;
}
else if(n&1){
int p = pow2(x, (n-1)/2)
return x * p * p;
}
else {
int p = pow2(x, n/2)
return p * p;
}
}
t(n)表示pow(x,n)所需的时间，即n的函数。t(0)=c，因为如果我们调用pow(x,0)，我们必须检查是否（n==0），然后返回1，这可以在恒定时间内完成（因此是常数c）。n>0。在这里，我们得到t(n) = d + t(n-1)。这是因为我们再次需要检查n==1，计算pow(x, n-1，因此（t(n-1)），并将结果乘以x。检查和乘法可以在恒定时间内完成（常数d），pow的递归计算需要t(n-1)。t(n)：t(n) =
d + t(n-1) =
d + (d + t(n-2)) =
d + d + t(n-2) =
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c
那么，我们需要多长时间才能到达t（1）？因为我们从t（n）开始，并且每一步减去1，所以需要n-1步才能到达t（n-（n-1））= t（1）。另一方面，这意味着我们获得了n-1次常数d，并且t（1）的值为c。
因此，我们得出：
t(n) =
...
d + d + d + ... + c =
(n-1) * d + c
所以我们得到 t(n)=(n-1) * d + c，它是 O(n) 的元素。
pow2 可以使用 主定理 进行计算。因为我们可以假设算法的时间函数单调递增。现在我们有了计算 pow2(x,n) 所需的时间 t(n)：
t(0) = c (since constant time needed for computation of pow(x,0))
对于 n>0，我们得到
/ t((n-1)/2) + d if n is odd (d is constant cost)
t(n) = <
\ t(n/2) + d if n is even (d is constant cost)
t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)
所以我们得到了 t(n) <= t(n/2) + d，可以使用主方法求解为 t(n) = O(log n)（请参见维基百科链接中的“流行算法应用”部分，例如“二分查找”的示例）。
让我们从 pow1 开始，因为它是最简单的。
你有一个函数，在 O(1) 的时间内完成一次运算。（条件检查，返回和乘法都是常量时间。）
剩下的就是递归了。你需要分析函数调用自身的次数。在 pow1 中，它会发生 N 次。N*O(1)=O(N)。
对于 pow2，原理相同 - 函数的单次运行时间为 O(1)。然而，这一次你每次都把 N 除以二。这意味着它将运行 log2(N) 次 - 每个位上实际上只运行一次。log2(N)*O(1)=O(log(N))。
有一件事可能会帮助你，那就是利用递归总是可以表达为迭代（虽然并不总是非常简单，但是这是可能的）。我们可以将 pow1 表示为
result = 1;
while(n != 0)
{
result = result*n;
n = n - 1;
}
现在你有了一个迭代的算法，你可能会发现这样分析更容易。
忽略递归，这两个函数的复杂度都是O(1)。
对于第一个算法pow1(x, n)，复杂度为O(n)，因为递归深度与n成线性相关。
对于第二个算法，复杂度为O(log n)。我们大约递归log2(n)次。去掉2，我们得到log n。
我猜测您是要将x的n次方。pow1的时间复杂度为O(n)。
您从未更改过x的值，但每次从n中减去1，直到它变为1（然后您只需返回）。这意味着您将进行n次递归调用。