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$$

另请参阅 #

切比雪夫不等式到底是个什么概念? - 马同学的回答 - 知乎