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)dy E[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>2
n>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,10
1,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_n
Mn?的一個遞推式
M
n
=
∑
j
=
1
n
1
n
E
[
X
∣
Y
]
M_n=\sum\limits_{j=1}^n \frac{1}{n}\mathrm{E}[X|Y]
Mn?=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-1
n?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_k
nMn?=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 1
Mn+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)?進而可以知道快速排序演算法的復雜度的期望是
n
log
?
n
n\log n
nlogn，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/419986.html
標籤：AI
上一篇：YOLOV5 環境搭建和使用記錄
下一篇：線性模型，SVM，決策樹