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

Рассмотрим проблему поиска «а» в массиве из n элементов.

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

Вывод: Найдите в массиве букву «а».

Мы даем две версии алгоритма, один алгоритм Лас-Вегаса и один алгоритм Монте-Карло.

Алгоритм Лас-Вегаса:

findA_LV (массив A, n)

начинать

повторить

Случайным образом выберите один элемент из n элементов.

пока не будет найдено 'a'

конец

Этот алгоритм работает с вероятностью 1. Количество итераций варьируется и может быть сколь угодно большим, но ожидаемое количество итераций равно

Поскольку оно постоянно, ожидаемое время выполнения для многих вызовов составляет

Алгоритм Монте-Карло:

findA_MC (массив A, n, k)

начинать

i: = 0

повторить

Случайным образом выберите один элемент из n элементов.

i: = i + 1

пока не будет найдено i = k или 'a'

конец

Если найден «а», алгоритм завершается успешно, иначе алгоритм не работает. После k итераций вероятность найти «а» равна:

Pr[find a] = 1- (1/2)^k

Этот алгоритм не гарантирует успеха, но время выполнения ограничено.

Количество итераций всегда меньше или равно k. Считая k постоянным,

время выполнения (ожидаемое и абсолютное) равно

Рандомизированные алгоритмы особенно полезны при столкновении со злонамеренным «противником» или злоумышленником, который намеренно пытается ввести неверный ввод в алгоритм (см. Сложность наихудшего случая и анализ конкуренции (онлайн-алгоритм)), например, в дилемме заключенного. По этой причине случайность в криптографии повсеместна. В криптографических приложениях нельзя использовать псевдослучайные числа, поскольку злоумышленник может их предсказать, что делает алгоритм эффективно детерминированным. Следовательно, требуется либо источник действительно случайных чисел, либо криптографически безопасный генератор псевдослучайных чисел. Еще одна область, которой присуща случайность, - это квантовые вычисления.

В приведенном выше примере алгоритм Лас-Вегаса всегда возвращает правильный ответ, но время его выполнения является случайной величиной. Алгоритм Монте-Карло (связанный с методом Монте-Карло для моделирования) гарантированно завершится за время, которое может быть ограничено функцией размером входных данных и ее параметром k, но допускает небольшую вероятность ошибки. Обратите внимание, что любой алгоритм Лас-Вегаса может быть преобразован в алгоритм Монте-Карло (с помощью неравенства Маркова), если он выдает произвольный, возможно, неправильный ответ, или если он не может быть выполнен в течение указанного времени. И наоборот, если существует эффективная процедура проверки для проверки правильности ответа, то алгоритм Монте-Карло может быть преобразован в алгоритм Лас-Вегаса путем многократного выполнения алгоритма Монте-Карло до получения правильного ответа.