13. 递归算法的时间复杂度分析

简介

我们在计算算法的时间复杂度的时候，往往会发现递归算法的时间复杂度非常复杂，因此，我们对其进行数学建模，致力于从递归数学表达式快速推导出时间复杂度
本文将从线性递归关系和树形递归关系分类进行分析
同时，本文将使用到的数学理论包括: 线性递归关系, 形式幂级数 , 二项式定理, 渐进表示法

线性递归算法分析

对于线性递归的算法，我们最常见的就是斐波那契数列，对于此类函数，我们统一进行建模:

$a_n = \alpha a_{n-1} +\beta a_{n-2} + f(n)$

在高中的时候，或许我们会使用所谓“特征根法”对方程进行求解化简，但是作为大学生，我们应该要想到将 $a_n$ 空间映射到别的空间中进行化简运算。这里形式幂级数给我们提供了很好的工具。我们可以将 $a_n$ 映射到 $A(x)$ 空间中，那么我们有

$A(x) = \alpha x (A(x) - a_0) + \beta x^2 (A(x) - a_0 - a_1 x) + F(x)$

这样，如果获得了 $F(x)$ 的具体形式，我们就有了 $A(x)$ 的公式表示

余项变换方式

$n^t$ 形式

对于余项 $f(n)$ 中包含 $n^t$ 的情况，首先在形式幂级数空间中变换为 $\sum_{n = 0}^\infty n^t x^n$
然而，我们要获得精确的解，就需要将级数变成 closed-form 即将求和的上限变为有限的值
那么我们很容易就会想到几何级数化简 (参考二项式定理))
那么我们就必须从 $\sum_{n = 0}^\infty x^n$ 变换为 $\sum_{n = 0}^\infty n^t x^n$
那么这个多出来的 $n^t$ 我们就很容易联想到 求导

$D(\sum_{n = 0} x^n) = \sum_{n = 1} n x^{n-1}$

而在几何级数变换空间，我们有

$D(\frac{1}{1-x}) = \frac{1}{(1-x)^2}$

二者相等，我们有 $\sum_{n = 1}^\infty n x^n = \frac{x}{(1-x)^2}$
同理，不断求导，我们就能获得更高次的求解结果

$2^n$ 形式

将这个项变成 $\sum_{n = 0}^\infty 2^n x^n = \sum_{n = 0}^\infty (2x)^n = \frac{1}{1 - 2x}$

$n^2 2^n$ 形式

通过形式幂级数变换，我们可以得到 $\sum n^2 (2 x)^n$ 再重复 求导过程就可以得到化简结果

$\sum a_ka_{n-k}$ 形式

这就是常见的卷积形式，我们常常需要通过卷积代换得到 $A^2(x)$ 形式

树形递归方法