假设一个随机过程 X的 n元素:X={x1,...,xn} .
对于给定的概率 p ，对应的分位数通过分位数函数Q确定定义为:
Q(p)={x|Pr(X<=x)=p}
找到给定概率的分位数的时间复杂度是多少p ？
最佳答案
Quickselect可以使用中位数枢轴选择的中位数来获得 O(n) 最坏情况运行时间来选择第 k 阶统计量。这似乎或多或少是你所追求的，除非我误解了(你想要第 (n*p) 个最小的元素)。
在一般情况下，您不可能对此进行改进:您必须至少查看整个数组，否则您没有查看的元素可能就是您需要的答案。
因此，Quickselect 理论上在最坏情况下是最优的。注意:这种枢轴选择策略有错误的常量，在实践中没有使用。在实践中，使用随机枢轴选择可提供良好的预期性能，但最坏情况为 O(n^2)。
关于algorithm - 找到给定概率的分位数的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48431410/