Сложность алгоритма, содержащего рандомную операцию

#алгоритм #сложность #асимптотика

Для всякого ли алгоритма можно оценить сложность при помощи О нотации?

Допустим, я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать
их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное. Конечно,
это очень кривой подход (в плане доступа к кэшам, например), но можно ли оценить его
алгоритмическую сложность?
    

Ответы

Ответ 1

Да, можно. Следует оценивать с учётом вероятности.

Например, сложность bogosort оценивается как



  я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать
их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное. 


Если в массиве около половины чисел чётные, то O(1).
Если только одно число чётное, то O(n) с жирненькой константой.
Если ни одного, то алгоритм вообще не завершится.

Если рассматривать случайный (равномерный) массив, то, вероятно, будет сводиться
к O(1) - как доступ по ключу хэш-таблицы.

PS: Провёл эксперимент для случая с единственным искомым числом (результат смотреть
в реальной консоли, открытой до запуска сниппета; при запуске браузер может зависнуть
на несколько секунд):



function go(n) {
  while (Math.random() * n | 0);
}

var res = [];

function check(n) {
  var t = performance.now();
  go(1< x+y)
  }
}

console.table(res.map(stat));






При удвоении длины время увеличивается вдвое, т. е. действительно O(n).