Почему рандомизированные алгоритмы могут быть быстрее и эффективнее детерминированных аналогов?

Question

Борис Державец · Accepted Answer

Рассмотрим проблему поиска «а» в массиве из n элементов.
Вход: массив из n≥2 элементов, половина из которых - «a», а другая половина - «b».
Вывод: Найдите в массиве букву «а».
Мы даем две версии ал...

Леонид Никифоров · Answer

1. Предположим, ваша постановка задачи такова, что ответ находится в доверительном интервале или, точнее, - имеет вероятностную природу.
2. Тогда рандомный поиск может быть быстрее.

Теперь Кью работает в режиме чтения

Почему рандомизированные алгоритмы могут быть быстрее и эффективнее детерминированных аналогов?