我对算法的预期执行时间和最坏情况执行时间有一个疑问，我认为是一个简单的算法，但这包含一个无限循环，我不知道如何解释预期的执行时间？我总是可以确定具有停止条件的算法的时间。
这是我的例子(我只知道，超过 n/2 可以给出 true(：
while (true)
{
int i = random(0,n-1);
bool e = decision(i); //Θ(n)
if (e==true)
return i;
}
预期的执行时间为 O(n(。
在概率p >= 1/2的情况下，第一个i会给出decision(i) == true，所以循环将在一次调用decision后终止。
q = 1 - p让它成为它没有发生的可能性。 然后，在概率q * p的情况下，第二个i会给出decision(i) == true，所以循环将在两次调用decision后终止。
类似地，对于概率q^2 * p，第三个i会给出decision(i) == true，所以循环将在三次调用decision后终止，依此类推。
通过取总和，我们得到了预期的调用数decision1 + q + q^2 + q^3 + .... 如q <= 1/2，总和最多为1 + 1/2 + 1/4 + 1/8 + ...，其上限为2。 因此，预期的呼叫次数受2的限制。
总的来说，由于每次调用decision都需要O(n)时间，因此预期的运行时间为O(2*n)，由于2是一个常量，因此仍然O(n)。
这似乎取决于决策最终为真的概率。 因此，在这种情况下，决策需要 n 个步骤。 这意味着运行时为 O(n(， 现在我们假设决策为真的概率，假设 50%，这意味着在平均情况下，我们需要每个循环 2n 步( sum(prob^x*n( ， x=0..infinity ，prob=0.5(。 即使 O 增加决策概率，乘法仍然线性绑定到"决策"为真的变化，因此 Stil O(n(。