使用 Python 实现 xn 的递归计算：
def f(x, n):
if n == 0:
return 1
else:
return x * f(x, n-1)
AI 代码解读
我们定义用来计算时间复杂度的函数为 T, 则上面的 xn 的递归计算可以使用如下递推关系来表示：
T(n)=T(n−1)+1
这样，有 T(n)=T(n−i)+i, 故而
T(n)=T(n−(n−1))+n−1=T(1)+n−1=Θ(1)+n−1=Θ(n)
其中，f∈Θ(g) 表示：存在自然数 n0 和正数 cc1,c2, 对于所有的 n≥n0 都成立
c1g(n)≤f(n)≤c2g(n).
综上所述，xn 在上面的递归定义下的时间复杂度为 Θ(n).
