让 0 < a < 0.5保持不变。我们有一个 n-element数组作为输入。随机快速排序从数组中随机均匀地选择一个元素作为枢轴和分区。最小部分大于an的概率是多少？ .我在注释中的简短回答很有可能1-2a .任何人都可以说这个概率是如何计算的？
最佳答案
较小分区的大小均匀分布在 [0, n/2] 范围内，因此它会小于 an 的概率是 an / (n/2) .所以它大于a的概率是 1 - an / (n/2) . an/(n/2)正是2a ，因此概率 1 - 2a .
这是一张图表，以防万一:
Pivot positions
a·n n/2 a·n+n/2 n
v v v v
<---------------------|||||||·---------------------|||||||>
/---^---\ /---^---\
smaller partition on left smaller partition on right
bigger than a·n bigger than a·n
size: n/2 - a·n size: n - (a·n + n/2)
Total size: n - 2a·n
Probability: 1 - 2a
关于sorting - 在某些条件下快速排序中分区中的最小部分？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35395064/