推出一个挺有意思的结论，随手记录一下。
令 T(n) 为算法在数据规模 = n 时的运算次数上界，满足
T(n) = \sum_{i = 1}^n f_i \ T(n - i)
特征方程为
x^n - \sum_{i = 0}^{n - 1} x^i f_{n-i} = 0
设有 n 个两两互异的复根 x_1,x_2,\cdots,x_n，则 \exists A_1, A_2, \cdots, A_n 满足
T(n) = \sum_{i = 1}^n x_i^n A_i
根据 |x_i^n| = |x_i|^n，可得 x_i^n 的实部不超过 |x_i|^n。
令
\alpha = \max_{1 \le i \le n} \{|x_i|\}
则
T(n) = O(\alpha^n)
更进一步，若存在重根，仍有
T(n) = O(\alpha^n \text{poly}(n))
例题：求 T(n) = T(n - 1) + T(n - 4) 的级别。
解法：方程的四个解为 x_1 \approx -0.724492，x_2 \approx -0.248126 - 1.03398 \mathrm{i}，x_3 \approx -0.248126 + 1.03398 \mathrm{i}，x_4 \approx 1.22074，无重根，且 T(n) = O(1.22074^n)。