63
правки
Изменения
→Алгоритм
Задан массив <tex>A</tex> в котором половина чисел единицы, а половина нули. Найти позицию какой-нибудь единицы.
====Алгоритм==== Выбираем случайную позицию и проверяем стоит ли на этой позиции единица. Если да то берем если нет про продолжаем пока не найдем. Ассимптотика - <tex></tex> Хоть у этого алгоритма такая же ассимптотика как и у алгоритма который просто начиная с первой позиции перебирает все числа, у этого алгоритма есть приемущество перед детерминированным. Для детерминированного алгоритма можно подобрать такой вход на котором он будет гарантированно работать плохо. А для рандомизированного нельзя.
===Проверка числа на простоту ===
