algorithm - 用递归分析特定算法的运行时间

Question

我将如何计算该算法的运行时间，以便将来可以解决类似的问题？

对于输入大小 n 满足递归关系（对于 n>= 1）

T(n) = (2/n) * (T(0) + T(1) + ... + T(n-1)) + 5n

Answer 1

摆脱总和的一种方法是在乘以 $n$ 之后计算差异（允许我编写 LaTeX，即使本网站不使用它；我希望公式是可以理解的）：

$$ (n + 1) a_{n + 1} - n a_n = 2 a_n + 5 $$

$$ (n + 1) a_{n + 1} - (n + 2) a_n = 5 $$

这是一阶的线性递归。表格的重现：

$$ x_n - u_{n - 1} x_{n - 1} = f_n $$

可以通过除以求和因子$S_n = \prod_{0 \le k \le n} u_n$ 归结为和，得到：

$$ \frac{x_n}{S_n} - \frac{x_{n - 1}}{S_{n - 1}} = \frac{f_n}{S_n} $$

对 $1 \le n \le N$ 求和给出方程的解。

在您的特定情况下 $S_n = \prod_{0 \le k \le n} \frac{n + 2}{n + 1} = n + 1$，因此：

$$ \frac{a_{k + 1}}{k + 2} - \frac{a_k}{k + 1} = \frac{5}{(k + 1) (k + 2)} $$

\begin{align} \frac{a_n}{n + 1} - \frac{a_0}{1} &= 5 \sum_{0 \le k < n} \frac{1}{(k + 1) (k + 2} \ &= - 5 \sum_{0 \le k < n} \left( \frac{1}{k + 2} - \frac{1}{k + 1} \right) \ &= - 5 \left( \frac{1}{n + 1} - 1 \right) \ &= 5 \frac{n}{n + 1} \end{align}

最后：

$$ a_n = a_0 (n + 1) + 5 n $$