algorithm - 概率算法，最好的情况实例可以依赖于随机参数吗？

Question

给定这个概率算法（伪代码）：

p = random(1,n) // 1/n chance for each value ranging from 1 to n
if array[0] = p
{
loop that executes in tetha(n)
}
return 0; 

编辑：数组中的可能值为 1..n

我认为有一个最好的情况实例 (array[0] = p) 但是，这包括一个随机参数，我觉得它不正确。我是对还是错，为什么？

Answer 1

对于最佳案例分析，您不应该考虑概率因素，唯一需要的是只有一种情况可以发生（概率为正）。因此，最好的案例分析是array[0] != p。那么，时间复杂度为Theta(1)。

这与最坏情况分析相同。假设p是给定的（是否随机选择并不重要）。最坏情况的时间复杂度是O(n)。

但是，由于算法中明确存在随机因素，这里的合理选择是平均时间复杂度，即(n-1)/n + 1/n * Theta(n) = Theta(1). 因为，if将满足概率1/n和其他条件的条件是(n-1)/n。