1 条件期望
定义1（条件期望）：给定随机变量
和
，则有如下条件期望
如果
如果
的连续随机变量，则有
证明： 离散随机变量的证明方式与连续随机变量证明方式一致，具体的证明过程如下所示
证毕。
2 快速排序算法分析
假设有个不同的值
的一个集合，将它们按照递增次序排序，完成它的一个有效的算法是快速排序算法。当
时，该算法比较此二值，将它们置于合适的次序。当
时，它开始在
值中随机地选取一个，譬如
，然后将其它的
个值与
比较，以
记小于
的元素的集合，
记大于
的元素即集合，然后分别对集合
和
分别排序，所以，最后的次序由集合
元素的次序、
、集合
元素的次序排列组成。
假定元素集合是，
，
，
，
，
，
，随机选取一个（即这
个值中的每一个选取的概率都是
）。假如值
被选取，然后将其它
个值得每一个与
做比较得到
将集合排序得到
其次，在中随机选取一个，譬如取到的是
，而且将其它三个值与
作比较得到
最后将得到
该算法有效性的一个度量是做次数的期望。假定以记
个不同值的一个集合的快速排序算法的比较次数的期望。令比较次数的随机变量为
，取到的第
小的值的随机变量为
，则此时可以得到
的一个递推式
若初始的取值是第小的值，则较小的集合的容量是
，较大的集合的容量是
。因此，由于对于选定的初始的取值需要作
次比较，可以得到
其中，等价于
为了求解上式，用代替
得到
因此，经过相减得到
进一步则有
所以
将此式迭代给出
从而
利用恒等式
，则可以得到如下近似
进而可以知道快速排序算法的复杂度的期望是。
版权声明：本文为博主鬼道2022原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/qq_38406029/article/details/122648243
