Algs4-2.3.10快排100万元素对比次数超1000亿次的概率

2.3.10Chebyshev不等式表明,一个随机变量的标准差距离均值大于k的概率小于1/k^2。对于N=100万,用Chebyshev不等式计算快速排序所使用的比较次数大于1000亿次的概率(0.1N^2)。
答:4.225*10^-9
切比雪夫不等式:P(|X-E(X)|>=r)<=V(X)/r^2
V(X)=q^2
q=0.65N (教材正文有分析过程中有提到)
r^2=1000亿的平方=10^24
P(|X-E(X)|>=10^12)<=(0.65&10^7)^2/10^24
P(|X-E(X)|>=10^12)<=4.225*10^-9

原文地址:https://www.cnblogs.com/longjin2018/p/9860205.html