2.3.10

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

解答

切比雪夫不等式(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 \\
k=\frac{2N}{13}
$$
将 $ N=1,000,000 $ 代入
$$
P(|X-27,631,021|\geq 100,000,000,000)\leq 0.00000000004225
$$

另请参阅

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

上一题 下一题