3.2.35

上次更新:2019-12-23
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

根据书中已经给出的归纳关系式(中文版P255/英文版P403):
$$
C_N=N-1+(C_0+C_{N-1})/N+(C_1+C_{N-2})/N+\cdots+(C_{N-1}+C_0)/N
$$
整理得:
$$
C_N=N-1+(C_0+C_1+\cdots+C_{N-1})/N+(C_{N-1}+\cdots+C_1+C_0)/N
$$
这和快速排序的式子基本一致,只是 $ N+1 $ 变成了 $ N-1 $。

遵循相同的推导过程,我们可以获得类似的结果,两边同乘以 $ N $:
$$
NC_N=N(N-1)+2(C_0+C_1+\cdots+C_{N-1})
$$
用 $ N+1 $ 时的等式减去该式得:
$$
(N+1)C_{N+1}-NC_N=2N+2C_N \\
(N+1)C_{N+1}=2N+(N+2)C_N \\
\frac{C_{N+1}}{N+2}=\frac{2N}{(N+1)(N+2)} + \frac{C_N}{N+1}
$$
令 $ T_N = \frac{C_N}{N+1} $,得到:
$$
T_{N+1}=\frac{2N}{(N+1)(N+2)} + T_N \\
T_{N+1}-T_{N} = \frac{2N}{(N+1)(N+2)}
$$
归纳得:
$$
\begin{aligned}
T_N &= 2 \sum_{i=2}^{N} \frac{i-1}{i(i+1)} \\
C_N&=2(N+1)\sum_{i=2}^{N} \frac{i-1}{i(i+1)} \\
C_N&=2(N+1)\sum_{i=2}^{N}(i-1) (\frac{1}{i}-\frac{1}{i+1}) \\
C_N&=-2(N-1)+ 2(N+1)\sum_{i=2}^{N}\frac{1}{i}\\
C_N&=-2(N-1)+ 2(N+1)(-1+\sum_{i=1}^{N}\frac{1}{i})\\
C_N&=-4N+2(N+1)(\ln N+\gamma)
\end{aligned}
$$
于是平均成本为:$ 1+C_N/N \sim 2\ln N+2\gamma-3 $ 。

上一题 下一题