Как получить ожидаемое время выполнения и наихудший случай для алгоритмов с бесконечным циклом?

Question

У меня есть одно сомнение относительно ожидаемого времени выполнения и наихудшего времени выполнения алгоритмов, я думал, что это простой алгоритм, но он содержит бесконечный цикл, и я не знаю, как объяснить это ожидаемое время выполнения ?.Я всегда мог определить время для алгоритмов с условиями остановки.

Это мой пример (я просто знаю, что больше чем n / 2 может дать истину):

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

Answer 1

Ожидаемое время выполнения 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 является константой.

Answer 2

Кажется, в зависимости от вероятности того, что решение окажется верным. Таким образом, в этом случае решение принимает n шагов. Это означает, что время выполнения O (n), Теперь мы берем вероятность того, что решение будет правдой, допустим, 50%, что означает, что в среднем нам нужно 2n шагов за цикл (сумма (prob ^ x * n), x = 0..infinity, prob = 0.5). Даже если O увеличивается с вероятностью принятия решения, умножение все еще линейно связано с изменением «решения», являющимся истинным, и, следовательно, все еще O (n).