Изменения

Выбираем случайную позицию и проверяем стоит ли на этой позиции единица. Если да то берем если нет про продолжаем пока не найдем. Ассимптотика {{- --}} <tex>\lim\limits_{n \to \infty}\sum\limits_{i=1}^n \frac{i}{2^i} = 2</tex>

Хоть у этого алгоритма такая же ассимптотика как и у детерминированного алгоритма , который просто начиная с первой позиции перебирает все числа, у этого рандомизированного алгоритма есть приемущество перед детерминированным. Для детерминированного алгоритма можно подобрать такой вход на котором он будет гарантированно работать плохо. А для рандомизированного нельзя.