查找给定概率的分位数的时间复杂度

Question

假设n元素的随机过程X：X={x1,...,xn} .

对于给定的概率p，相应的分位数通过分位数函数确定，Q定义为：

Q(p)={x|Pr(X<=x)=p}

找到给定概率p的分位数的时间复杂度是多少？

Answer 1

快速选择可以使用中位数枢轴选择来获取 O(n( 最坏情况运行时以选择 k 阶统计量。这似乎或多或少是你所追求的，除非我误解了(你想要(n*p(的最小元素(。

在一般情况下，你不可能改进这一点：你至少必须查看整个数组，否则你没有看到的元素可能是你需要的答案。

因此，在最坏的情况下，快速选择在理论上是最佳的。注意：此枢轴选择策略具有错误的常量，在实践中未使用。在实践中，使用随机枢轴选择可提供良好的预期性能，但 O(n^2( 最坏情况。