问随机快速排序:低分区大小的概率为1
EN

Stack Overflow用户

提问于 2016-10-18 16:01:25

回答 1查看 140关注 0票数 2

在随机快速排序中，得到大小为1的低分区的概率是2/n。我一直在尝试解决这个问题，但不知道如何解决。

我得到的表达式是：

X = low partition size
P(X=1) = 1/n + 1/n
[Summation(i = 2 to n) 
{
  (n-i Comb i-1)/(n-1 Comb i-1)
}
]

这将简化为：

= 1/n + 1/n[(n-2)/(n-1) + (n-3)(n-4)/(n-1)(n-2) + ...]

如何走得更远？我的方法和表达是正确的吗？

发布于 2016-10-18 16:26:35

得到大小为1的低分区的概率为2/n

这取决于你所说的“大小为1的低分区”的意思。如果你看一下worst case for quicksort

发生最不平衡的分区..如果透视恰好是列表中最小或最大的元素

对于均匀选择，选择最低元素的概率是1/ n，选择最高元素的概率也是1/n。由于这些是不相交的事件(当元素不完全相同时)，因此总的概率是它们的和:2/ n。

分区左侧为1的概率是1/ n的一半。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/40102742

复制

相似问题

问随机快速排序:低分区大小的概率为1EN