如何获得无限循环算法的预期执行时间和最坏情况？
How to obtain expected execution time and worst case for algorithms with infinite loop?
我对算法的预期执行时间和最坏情况下的执行时间有一个疑问，我认为这是一个简单的算法，但它包含一个无限循环，我不知道如何解释预期的执行时间？。我总是可以确定具有停止条件的算法的时间。
这是我的例子（我只知道，比n/2更能给真）：
while (true)
{
int i = random(0,n-1);
bool e = decision(i); //Θ(n)
if (e==true)
return i;
}
这似乎取决于决定最终成真的概率。
所以在这种情况下，决策需要 n 个步骤。
这意味着运行时间是 O(n)，
现在我们采用决策为真的概率，假设为 50%，这意味着平均每个循环需要 2n 步（sum(prob^x*n)，x=0..infinity，prob=0.5）。
尽管 O 增加了决策概率，乘法仍然与 "decision" 为真的变化线性相关，因此仍然是 O(n).
预计执行时间为 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之后终止，依此类推。
通过求和，我们得到对 decision 的预期调用次数
1 + q + q^2 + q^3 + ...。
由于q <= 1/2，总和最多为1 + 1/2 + 1/4 + 1/8 + ...，上限为2。
因此，预期调用次数受 2.
限制
总的来说，由于每次调用 decision 需要 O(n) 时间，因此 运行 的预期时间是 O(2*n)，这仍然是 O(n)，因为 2 是常数。
我对算法的预期执行时间和最坏情况下的执行时间有一个疑问，我认为这是一个简单的算法，但它包含一个无限循环，我不知道如何解释预期的执行时间？。我总是可以确定具有停止条件的算法的时间。
这是我的例子（我只知道，比n/2更能给真）：
while (true)
{
int i = random(0,n-1);
bool e = decision(i); //Θ(n)
if (e==true)
return i;
}
这似乎取决于决定最终成真的概率。 所以在这种情况下，决策需要 n 个步骤。 这意味着运行时间是 O(n)， 现在我们采用决策为真的概率，假设为 50%，这意味着平均每个循环需要 2n 步（sum(prob^x*n)，x=0..infinity，prob=0.5）。 尽管 O 增加了决策概率，乘法仍然与 "decision" 为真的变化线性相关，因此仍然是 O(n).
预计执行时间为 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之后终止，依此类推。
通过求和，我们得到对 decision 的预期调用次数
1 + q + q^2 + q^3 + ...。
由于q <= 1/2，总和最多为1 + 1/2 + 1/4 + 1/8 + ...，上限为2。
因此，预期调用次数受 2.
总的来说，由于每次调用 decision 需要 O(n) 时间，因此 运行 的预期时间是 O(2*n)，这仍然是 O(n)，因为 2 是常数。