我将如何计算该算法的运行时间，以便将来解决类似问题？
For input size n satisfies the recurrence relation (for n>= 1)
T(n) = (2/n) * (T(0) + T(1) + ... + T(n-1)) + 5n
最佳答案
消除和的一种方法是在乘以 $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)} $$
\开始{对齐} \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} \结束{对齐}
最后:
$$ a_n = a_0 (n + 1) + 5 n $$
关于algorithm - 带递归的具体算法运行时间分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23305144/