Лас-Вегас — вид вероятностного алгоритма.
Идея алгоритма Лас-Вегас состоит в следующем. Если у нас есть некий вероятностный алгоритм , который с определённой вероятностью даёт верный результат, и существует возможность алгоритмически проверить результат алгоритма на корректность (скажем, с помощью алгоритма ), то можно выполнять алгоритм до тех пор, пока проверка не установит, что результат верен:
Выполнить алгоритм с результатом до тех пор, пока не будет истиной.
Название этому принципу было дано с одной стороны как намек на метод Монте-Карло. С другой стороны это название намекает на «метод выигрыша в казино», которое схоже с процессом работы алгоритма — «если я буду играть ещё и ещё, я когда-нибудь обязательно выиграю».
Следует заметить, что алгоритм Лас-Вегаса гарантирует получение правильного результата. Алгоритм работает за конечное, но не детерминированное время. Можно указать только вероятность получения результата за заданное время.
Примеры Данный псевдокод можно назвать примером алгоритма Лас-Вегас:
function lasvegas() begin var a := random();
if(verify(a) = true) then return a; end
Примером алгоритма, относящегося к классу Лас-Вегас, является алгоритм сортировки Bogosort: данные, которые нужно отсортировать, перемешиваются случайным образом, и затем проверяется, оказались ли они расположенными в нужном порядке. В случае неудачи перемешивание многократно повторяется вплоть до достижения желаемого порядка.
Связь с алгоритмами Монте-Карло Пусть — алгоритм Лас-Вегаса с ожидаемой временной сложностью , где — длина входа. Оценим снизу вероятность того, что решение для произвольного входа длины будет найдено , а значит и алгоритмом Монте-Карло , менее чем за шагов, считая . Пусть — время работы , тогда , и согласно неравенству Маркова: .
Откуда искомая сразу следует искомая оценка .
Ссылки Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999 «Las Vegas algorithm» / Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. NIST. 17 July 2006.
Категория:Алгоритмы