Quickselect时间复杂度

Question

我想要计算快速选择算法中的平均比较数。我知道平均运行时是O(n)，但也需要知道常量。所以上网寻找答案，但当我读到不同的解决方案时，我感到很困惑。是4n还是3n？不然呢？有谁可以帮我？提前感谢

Answer 1

是O(n)。您感兴趣的常量取决于分区的完成方式。它因枢轴的不同而不同。这就是为什么cn是c常量的原因。(可以是4、3或5等)。

最坏的情况可以是O(n^2)平均情况下的O(n)。这就是你所能肯定的。