在quickSort中，期望值(数学)是什么意思?它背后的原因是什么？
在quickSort中，期望值(数学)是什么意思?它背后的原因是什么？
提问于 2019-11-03 19:17:02
我需要帮助解释来自Clrs书中的快速排序算法描述，第157页的公式
我的问题被堆叠在页面截图中。这个公式是关于QiuckSort算法的。
- (逻辑)前.我的意思是，作者写这个公式的“快速启动”是怎么回事？
- 给定n=3，结果是8，好的，但在快速排序中8的语义意义是什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-11-03 19:47:12
为了理解你引用的书中的分析，你需要从概率论中理解一些概念。
我们想要确定快速排序的平均比较数。
我们定义了一些随机变量。如果比较了X_ij和z_j，则为1，否则为0。X是比较总数的随机变量。因此X= X_ij的I和j上的和。
EX是X的期望值，即“平均值”。期望是线性的，所以和的期望等于期望的和。这就是本书的结论，即比较的平均数量等于i和j的EX_ij之和。由于X_ij为0或1，其期望值与z_i和z_j之间进行比较的概率相同。
如果您在跟踪这方面仍然有困难，则需要阅读概率、随机变量和期望值。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58683766
复制相关文章
相似问题
腾讯云开发者
