2.3.10 #
解答 #
切比雪夫不等式（Chebyshev’s inequality）
$$ P(|X-\mu|\geq k\sigma)\leq \frac{1}{k^2} $$
其中，$\mu$ 代表期望，$\sigma$ 代表标准差。
对于快速排序的比较次数来说，$\mu = 2N\ln N$ ，$\sigma=0.65N$。
（这两个结论见 2.3 节的命题 K 和命题 L）
题目中要求比较次数大于 $0.1N^2$ ，可以求得 $k$ 的值。
$$ 0.65kN=0.1N^2 \newline k=\frac{2N}{13} $$
将 $N=1,000,000$ 代入
$$ P(|X-27,631,021|\geq 100,000,000,000)\leq 0.00000000004225 $$