<>1 条件期望

定义1(条件期望):给定随机变量 X X X和 Y Y Y,则有如下条件期望 E [ X ] = E [ E [ X ∣ Y ] ]
\mathrm{E}[X]=\mathrm{E}\left[\mathrm{E}[X|Y]\right]E[X]=E[E[X∣Y]]如果 Y Y Y
是离散随机变量,则有 E [ X ] = ∑ y E [ X ∣ Y = y ] P { Y = y }
\mathrm{E}[X]=\sum\limits_{y}\mathrm{E}[X|Y=y]\mathrm{P}\{Y=y\}E[X]=y∑​E[X∣Y=y]P
{Y=y}如果 Y Y Y是密度为 f Y ( y ) f_Y(y) fY​(y)的连续随机变量,则有 E [ X ] = ∫ − ∞ ∞ E [ X ∣ Y
= y ] f Y ( y ) d y
\mathrm{E}[X]=\int_{-\infty}^{\infty}\mathrm{E}[X|Y=y]f_Y(y)dyE[X]=∫−∞∞​E[X∣Y=y]
fY​(y)dy

证明: 离散随机变量的证明方式与连续随机变量证明方式一致,具体的证明过程如下所示 ∑ y E [ X ∣ Y = y ] P ( Y = y ) = ∑ y
∑ x x P { X = x ∣ Y = y } P { Y = y } = ∑ y ∑ x x P { X = x , Y = y } P { Y = y
} P ( Y = y ) = ∑ y ∑ x x P { X = x , Y = y } = ∑ x x ∑ y P { X = x , Y = y } =
∑ x x P { X = x } = E [ X ] \begin{aligned}\sum\limits_y
\mathrm{E}[X|Y=y]\mathrm{P}(Y=y)&=\sum\limits_y\sum\limits_{x}x
\mathrm{P}\{X=x|Y=y\}\mathrm{P}\{Y=y\}\\&=\sum\limits_y
\sum\limits_{x}x\frac{\mathrm{P}\{X=x,Y=y\}}{\mathrm{P}\{Y=y\}}\mathrm{P}(Y=y)\\&=\sum\limits_{y}\sum\limits_xx\mathrm{P}\{X=x,Y=y\}\\&=\sum\limits_{x}x\sum\limits_{y}\mathrm{P}\{X=x,Y=y\}\\&=\sum\limits_{x}x\mathrm{P}\{X=x\}=\mathrm{E}[X]\end{aligned}
y∑​E[X∣Y=y]P(Y=y)​=y∑​x∑​xP{X=x∣Y=y}P{Y=y}=y∑​x∑​xP{Y=y}P{X=x,Y=y}​P(Y=y)=y∑​x∑​
xP{X=x,Y=y}=x∑​xy∑​P{X=x,Y=y}=x∑​xP{X=x}=E[X]​证毕。

<>2 快速排序算法分析

 假设有 n n n个不同的值 x 1 , ⋯   , x n x_1,\cdots,x_n x1​,⋯,xn​
的一个集合,将它们按照递增次序排序,完成它的一个有效的算法是快速排序算法。当 n = 2 n=2 n=2时,该算法比较此二值,将它们置于合适的次序。当 n >
2 n>2n>2时,它开始在 n n n值中随机地选取一个,譬如 x i x_i xi​,然后将其它的 n − 1 n-1 n−1个值与 x i x_i xi​
比较,以 S i S_i Si​记小于 x i x_i xi​的元素的集合, S i ˉ \bar{S_i} Si​ˉ​记大于 x i x_i xi​
的元素即集合,然后分别对集合 S i S_i Si​和 S i ˉ \bar{S_i} Si​ˉ​分别排序,所以,最后的次序由集合 S i S_i Si​
元素的次序、 x i x_i xi​、集合 S i ˉ \bar{S_i} Si​ˉ​元素的次序排列组成。
 假定元素集合是 10 10 10, 5 5 5, 8 8 8, 2 2 2, 1 1 1, 4 4 4, 7 7 7,随机选取一个(即这 7 7 7
个值中的每一个选取的概率都是 1 7 \frac{1}7{} 71​)。假如值 4 4 4被选取,然后将其它 6 6 6个值得每一个与 4 4 4做比较得到
{ 2 , 1 } , 4 , { 10 , 5 , 8 , 7 } \{2,1\},4,\{10,5,8,7\}{2,1},4,{10,5,8,7}将集合
{ 2 , 1 } \{2,1\}{2,1}排序得到 1 , 2 , 4 , { 10 , 5 , 8 , 7 } 1,2,4,\{10,5,8,7\} 1,2
,4,{10,5,8,7}其次,在 { 10 , 5 , 8 , 7 } \{10,5,8,7\} {10,5,8,7}中随机选取一个,譬如取到的是 7 7 7
,而且将其它三个值与 7 7 7作比较得到 1 , 2 , 4 , 5 , 7 , { 10 , 8 } 1,2,4,5,7,\{10,8\} 1,2,4,5,
7,{10,8}最后将 { 10 , 8 } \{10,8\} {10,8}得到 1 , 2 , 4 , 5 , 7 , 8 , 10
1,2,4,5,7,8,101,2,4,5,7,8,10该算法有效性的一个度量是做次数的期望。假定以 M n M_n Mn​记 n n n
个不同值的一个集合的快速排序算法的比较次数的期望。令比较次数的随机变量为 X X X,取到的第 j j j小的值的随机变量为 Y Y Y,则此时可以得到 M
n M_nMn​的一个递推式 M n = E [ X ] = E [ E [ X ∣ Y ] ] = ∑ j = 1 n 1 n E [ X ∣ Y ]
M_n=\mathrm{E}[X]=\mathrm{E}[\mathrm{E}[X|Y]]=\sum\limits_{j=1}^n
\frac{1}{n}\mathrm{E}[X|Y]Mn​=E[X]=E[E[X∣Y]]=j=1∑n​n1​E[X∣Y]若初始的取值是第 j j j
小的值,则较小的集合的容量是 j − 1 j-1 j−1,较大的集合的容量是 n − j n-j n−j。因此,由于对于选定的初始的取值需要作 n − 1
n-1n−1次比较,可以得到 M n = ∑ j = 1 n 1 n ( n − 1 + M j − 1 + M n − j ) = n − 1 + 2 n
∑ k = 1 n − 1 M k
M_n=\sum\limits_{j=1}^n\frac{1}{n}(n-1+M_{j-1}+M_{n-j})=n-1+\frac{2}{n}\sum\limits^{n-1}_{k=1}M_k
Mn​=j=1∑n​n1​(n−1+Mj−1​+Mn−j​)=n−1+n2​k=1∑n−1​Mk​其中 M 0 = 0 M_0=0 M0​=0,等价于 n M
n = n ( n − 1 ) + 2 ∑ k = 1 n − 1 M k nM_n = n(n-1)+2\sum\limits_{k=1}^{n-1}M_kn
Mn​=n(n−1)+2k=1∑n−1​Mk​为了求解上式,用 n + 1 n+1 n+1代替 n n n得到 ( n + 1 ) M n + 1 = ( n
+ 1 ) n + 2 ∑ k = 1 n M k (n+1)M_{n+1}=(n+1)n+2\sum\limits_{k=1}^nM_k(n+1)Mn+1​=
(n+1)n+2k=1∑n​Mk​因此,经过相减得到 ( n + 1 ) M n + 1 − n M n = 2 n + 2 M n
(n+1)M_{n+1}-nM_n=2n+2M_n(n+1)Mn+1​−nMn​=2n+2Mn​进一步则有 ( n + 1 ) M n + 1 = ( n +
2 ) M n + 2 n (n+1)M_{n+1}=(n+2)M_n+2n(n+1)Mn+1​=(n+2)Mn​+2n所以 M n + 1 n + 2 =
2 n ( n + 1 ) ( n + 2 ) + M n n + 1
\frac{M_{n+1}}{n+2}=\frac{2n}{(n+1)(n+2)}+\frac{M_n}{n+1}n+2Mn+1​​=(n+1)(n+2)2n​
+n+1Mn​​将此式迭代给出 M n + 1 n + 2 = 2 n ( n + 1 ) ( n + 2 ) + 2 ( n − 1 ) n ( n + 1
) + M n − 1 n = ⋯ = 2 ∑ k = 0 n − 1 n − k ( n + 1 − k ) ( n + 2 − k )
\begin{aligned}\frac{M_{n+1}}{n+2}&=\frac{2n}{(n+1)(n+2)}+\frac{2(n-1)}{n(n+1)}+\frac{M_{n-1}}{n}\\&=\cdots\\&=2\sum\limits_{k=0}^{n-1}\frac{n-k}{(n+1-k)(n+2-k)}\end{aligned}
n+2Mn+1​​​=(n+1)(n+2)2n​+n(n+1)2(n−1)​+nMn−1​​=⋯=2k=0∑n−1​(n+1−k)(n+2−k)n−k​​从而
M n + 1 = 2 ( n + 2 ) ∑ k = 0 n − 1 n − k ( n + 1 − k ) ( n + 2 − k ) = 2 ( n +
2 ) ∑ i = 1 n i ( i + 1 ) ( i + 2 ) , n ≥ 1
M_{n+1}=2(n+2)\sum\limits_{k=0}^{n-1}\frac{n-k}{(n+1-k)(n+2-k)}=2(n+2)\sum\limits_{i=1}^n\frac{i}{(i+1)(i+2)},\quad
n\ge 1Mn+1​=2(n+2)k=0∑n−1​(n+1−k)(n+2−k)n−k​=2(n+2)i=1∑n​(i+1)(i+2)i​,n≥1利用恒等式
i [ ( i + 1 ) ( i + 2 ) ] = 2 ( i + 2 ) − 1 ( i + 1 )
\frac{i}{[(i+1)(i+2)]}=\frac{2}{(i+2)}-\frac{1}{(i+1)}[(i+1)(i+2)]i​=(i+2)2​−(i+
1)1​,则可以得到如下近似 M n + 1 = 2 ( n + 2 ) [ ∑ i = 1 n 2 i + 2 − ∑ i = 1 n 1 i + 1 ]
∼ 2 ( n + 2 ) [ ∫ 3 n + 2 2 x d x − ∫ 2 n + 1 1 x d x ] = 2 ( n + 2 ) [ 2 ln ⁡
( n + 2 ) − ln ⁡ ( n + 1 ) + ln ⁡ 2 − 2 ln ⁡ 3 ] = 2 ( n + 2 ) [ ln ⁡ ( n + 2 )
+ ln ⁡ n + 2 n + 1 + ln ⁡ 2 − 2 ln ⁡ 3 ] ∼ 2 ( n + 2 ) ln ⁡ ( n + 2 )
\begin{aligned}M_{n+1}&=2(n+2)\left[\sum\limits_{i=1}^n\frac{2}{i+2}-\sum\limits_{i=1}^n\frac{1}{i+1}\right]\\&\sim2(n+2)\left[\int_3^{n+2}\frac{2}{x}dx-\int_2^{n+1}\frac{1}{x}dx\right]\\&=2(n+2)[2\ln(n+2)-\ln(n+1)+\ln
2 - 2\ln 3]\\&=2(n+2)\left[\ln(n+2)+\ln\frac{n+2}{n+1}+\ln2 - 2\ln
3\right]\\&\sim 2(n+2)\ln(n+2)\end{aligned}Mn+1​​=2(n+2)[i=1∑n​i+22​−i=1∑n​i+11​
]∼2(n+2)[∫3n+2​x2​dx−∫2n+1​x1​dx]=2(n+2)[2ln(n+2)−ln(n+1)+ln2−2ln3]=2(n+2)[ln(n+
2)+lnn+1n+2​+ln2−2ln3]∼2(n+2)ln(n+2)​进而可以知道快速排序算法的复杂度的期望是 O ( n log ⁡ n )
O(n\log n)O(nlogn)。

技术
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信