如何分析随机化数组查找1算法的最优、平均与最坏情况性能？

先看给定的算法代码：

while True:
     i = random(1, n)
     if a[i] == 1:
         return i

数组a[1..n]中一半元素是0，一半是1，我们从三个维度分析性能：

最优情况性能 #

最优情况就是第一次随机选取的位置直接命中值为1的元素，只需要执行1次随机生成操作和1次条件判断，就能返回结果。

• 时间复杂度：O(1)
• 说明：这种情况发生的概率是1/2，但最优性能关注的是算法完成任务所需的最少步骤，所以取这个最小次数。

平均情况性能 #

这个算法的每次尝试都是独立的伯努利试验：每次随机选位置，选中1的概率是p = 1/2（因为一半元素是1），选中0则继续循环。这符合几何分布，几何分布的期望（即平均尝试次数）是1/p = 2。

• 平均尝试次数：2次
• 时间复杂度：O(1)
• 说明：每次迭代都是O(1)的操作，所以整体平均时间复杂度是常数级。

最坏情况性能 #

由于算法是随机选取位置，理论上存在一种极端情况：无限次选中值为0的元素，导致循环永远无法终止。

• 时间复杂度：O(∞)（无上限）
• 说明：这种情况发生的概率趋近于0，但从理论最坏情况的定义来看，算法的执行时间没有上界。

内容的提问来源于stack exchange，提问作者Colab Google