一个递归计算与时间复杂度分析的例子
使用 Python 实现 $x^n$ 的递归计算：
def f(x, n):
if n == 0:
return 1
else:
return x * f(x, n-1)我们定义用来计算时间复杂度的函数为 $T$, 则上面的 $x^n$ 的递归计算可以使用如下递推关系来表示：
$$ T(n) = T(n-1) + 1 $$
这样，有 $T(n) = T(n-i) + i$, 故而
$$ \begin{aligned} T(n) &= T(n-(n-1)) + n-1\\ &=T(1) + n-1\\ &=\Theta (1) + n-1\\ &=\Theta(n) \end{aligned} $$
其中，$f \in \Theta(g)$ 表示：存在自然数 $n_0$ 和正数 $cc_1,c_2$, 对于所有的 $n\geq n_0$ 都成立
$$ c_1g(n) \leq f(n) \leq c_2g(n). $$
综上所述，$x^n$ 在上面的递归定义下的时间复杂度为 $\Theta(n)$.
