预期值(数学)是什么意思，在quickSort中背后的原因是什么? [英] what is meaning expected value(math) and what reason behind it in quickSort?
问题描述
我需要帮助来解释 "Clrs"书第157页中的快速排序算法描述
我的问题被覆盖在页面截图中. 这个公式是关于QiuckSort算法的.
My questions are overlayed in the page screenshot. This formula is about QiuckSort Algorithm.
- (逻辑)E [X]后面是什么...我是说作者在开始快速入门时写了这个公式?
- 给定n = 3，结果为8，可以，但是8在快速排序中的语义是什么?
推荐答案
为了理解您引用的书中的分析，您需要了解概率论中的一些概念.
In order to understand the analysis in the book you cited, you need to understand some concepts from probability theory.
我们要确定quicksort进行比较的平均次数.
We want to determine the average number of comparisons made by quicksort.
我们定义了一些随机变量.如果将z_i和z_j比较，则X_ij = 1，否则为0. X是进行比较的总数的随机变量.因此，X = X_ij的i和j的和.
We define some random variables. X_ij = 1 if z_i and z_j are compared, and 0 otherwise. X is a random variable for the total number of comparisons made. Thus X = sum over i and j of X_ij.
E [X]是X的期望值，即平均"值.期望是线性的，因此总和的期望等于期望的总和.这就是该书得出的结论，即平均比较数等于E [X_ij]的i和j的总和.由于X_ij为0或1，因此其期望值与z_i和z_j之间进行比较的可能性相同.
E[X] is the expected value of X, i.e. the value "on average". Expectation is linear, so the expectation of a sum is equal to the sum of expectations. That's how the book concludes that the average number of comparisons is equal to the sum over i and j of E[X_ij]. Since X_ij is either 0 or 1, its expected value is the same as the probability of making a comparison between z_i and z_j.
如果您在执行此操作时仍然遇到困难，则需要阅读概率，随机变量和期望值.
If you're still have trouble following this, you'll need to read up on probability, random variables, and expected values.
这篇关于预期值(数学)是什么意思，在quickSort中背后的原因是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
