如何求解含无限循环的算法的期望执行时间与最坏情况？

你的示例算法代码是这样的对吧：

while (true) { 
    int i = random(0,n-1); 
    bool e = decision(i); //Θ(n) 
    if (e==true) return i; 
}

嘿，这个问题挺有意思的——随机算法的期望时间分析确实和咱们平时分析确定性算法的思路不太一样，尤其是这种靠概率终止的无限循环，我来一步步给你拆解清楚。

首先先明确几个从你的描述和代码里能推导出来的前提：

• random(0, n-1) 是均匀随机生成整数，每个i被选中的概率都是1/n；
• 满足 decision(i) = true 的i的数量超过n/2，也就是说单次循环里成功（直接返回i）的概率 p > 1/2；
• 每次调用 decision(i) 的时间复杂度是 Θ(n)，生成随机数的时间可以忽略（视为O(1)，毕竟只是个简单的随机数生成操作）。

1. 循环的期望次数：用几何分布搞定 #

你的算法本质就是在重复做伯努利试验：每次循环是一次试验，成功概率是p，直到第一次成功就停止。这种场景完美匹配几何分布——这个分布就是专门用来描述“首次成功需要多少次试验”的。

对于几何分布，首次成功的期望试验次数是 1/p。举个例子，如果p=3/4，那平均大概1.33次循环就能成功；如果p刚好略大于1/2（比如n很大的时候），那平均也就2次左右。

结合你说的“超过n/2的i会返回true”，p的最小值其实很好算：

• 当n是偶数时：成功的i有n/2 + 1个，p=(n/2 +1)/n = 1/2 + 1/n；
• 当n是奇数时：成功的i有(n+1)/2个，p=(n+1)/(2n) = 1/2 + 1/(2n)；

不管n是奇是偶，p都肯定大于1/2，所以 1/p 是个常数（最大也就接近2，当n无限大的时候）。

2. 单次循环的时间成本 #

每次循环里就两件事：

• 生成随机i：O(1)，没啥成本；
• 跑 decision(i)：Θ(n)，这是主要耗时；

所以单次循环的总时间复杂度就是 Θ(n)（O(1)被Θ(n)完全主导了）。

3. 总的期望执行时间 #

把上面两个部分乘起来就行：期望循环次数 × 单次循环时间，也就是：
E[T] = (1/p) × Θ(n)

因为1/p是个常数，所以整体的期望时间复杂度就是 Θ(n)。

额外说一句：无限循环真的没问题吗？ #

你可能会纠结“无限循环”这个点，但实际上这个算法几乎必然会终止——因为每次循环都有p>0的成功概率，无限次试验下来，至少成功一次的概率是1（概率学里的Borel-Cantelli引理能证明这一点），所以期望时间是有限的，完全可以用上面的方法分析。

举个具体的小例子：假设n=4，成功的i有3个（超过4/2=2），p=3/4，期望循环次数是4/3≈1.33次，每次循环耗时Θ(4)，总期望时间就是(4/3)*Θ(4)=Θ(4)=Θ(n)，完全符合咱们的结论。

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