问题及解答

设 $f(N)$ 满足下面的递推公式

\[
f(N)=\frac{2}{N}\Bigl[\sum_{j=0}^{N-1}f(j)\Bigr]+cN,
\]

其中 $c$ 是某个常数, 且已知 $f(0)=f(1)=0$, 求 $f(N)$ 的表达式.

在数据结构中会用到这个公式

根据题设,

\[
Nf(N)=2\sum_{j=0}^{N-1}f(j)+cN^2,\tag{1}
\]

用 $N-1$ 代替上面式子中的 $N$, 得到

\[
(N-1)f(N-1)=2\sum_{j=0}^{N-2}f(j)+c(N-1)^2.\tag{2}
\]

(1)-(2), 得

\[
Nf(N)-(N-1)f(N-1)=2f(N-1)+c(2N-1),
\]

整理即

\[
Nf(N)=(N+1)f(N-1)+c(2N-1).\tag{3}
\]

将 (3) 两边除以 $N(N-1)$, 得到

\[
\frac{f(N)}{N+1}=\frac{f(N-1)}{N}+\frac{c(2N-1)}{N(N+1)}.
\]

于是

\[\left\{
\begin{aligned}
\frac{f(N)}{N+1}&=\frac{f(N-1)}{N}+\frac{c(2N-1)}{N(N+1)}\\
\frac{f(N-1)}{N}&=\frac{f(N-2)}{N-1}+\frac{c(2N-3)}{(N-1)N}\\
\frac{f(N-2)}{N-1}&=\frac{f(N-3)}{N-2}+\frac{c(2N-5)}{(N-2)(N-1)}\\
&\vdots\\
\frac{f(2)}{3}&=\frac{f(1)}{2}+\frac{3c}{2\cdot 3}\\
\end{aligned}
\right.\]

将上面 $N-1$ 个式子相加, 整理得

\[
\frac{f(N)}{N+1}=\frac{f(1)}{2}+\sum_{j=2}^{N}\frac{c(2j-1)}{j(j+1)}.
\]

注意到

\[
\frac{1}{j}\leqslant\frac{2j-1}{j(j+1)}< \frac{2}{j},
\]

故

\[
c\sum_{j=2}^{N}\frac{1}{j}\leqslant\frac{f(N)}{N+1}< 2c\sum_{j=2}^{N}\frac{1}{j}.
\]

回忆 欧拉常数(Euler\'s constant) 的定义
(参见 http://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant)

\[
\gamma :=\lim_{n\rightarrow\infty}\biggl[\sum_{j=1}^{N}\frac{1}{j}-\ln N\biggr]
\]

因此 $\frac{f(N)}{N+1}=O(\log N)$, 即 $f(N)=O(N\log N)$.