3.2.35 #

解答 #

根据书中已经给出的归纳关系式（中文版 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 \newline (N+1)C_{N+1}=2N+(N+2)C_N \newline \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 \newline 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)} \newline C_N&=2(N+1)\sum_{i=2}^{N} \frac{i-1}{i(i+1)} \newline C_N&=2(N+1)\sum_{i=2}^{N}(i-1) (\frac{1}{i}-\frac{1}{i+1}) \newline C_N&=-2(N-1)+ 2(N+1)\sum_{i=2}^{N}\frac{1}{i}\newline C_N&=-2(N-1)+ 2(N+1)(-1+\sum_{i=1}^{N}\frac{1}{i})\newline C_N&=-4N+2(N+1)(\ln N+\gamma) \end{aligned} $$

于是平均成本为：$1+C_N/N \sim 2\ln N+2\gamma-3$ 。