Изменения

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

{{---}} Также доказано что для каждого нечетного составного <tex>N, |\{A \in [1\,..\,N - 1]: gcd(N, A) = 1</tex> и <tex>(\frac{N}{A}) = A^{\frac{N - 1}{2}}(mod \ N)\}| \le \frac{N}{2}</tex>