Увипадковлений алгоритм: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 53:
Цей алготитм не гарантує успіху, але його час виконання обмежений. Кількість ітерацій завжди менша ніж або рівна ''k''. Якщо ''k'' константа, то час виконання (очікуваний і абсолютний) це <math>\Theta(1)</math>.
Увипадковлені алгоритми особливо корисні коли маємо справу зі зловмисним «супротивником» або [[нападник (спорт)|нападником]], який зумисно намагається згодувати алгоритму погані входові дані (див. [[найгірший випадок складності]] і {{нп|
У горішньому прикладі, Лас-Вегасівський алгоритм завжди видає правильну відповідь, але його час виконання це випадкова величина. Алгоритм Монте-Карло (пов'язаний з [[Метод Монте-Карло|методом Монте-Карло]] для симуляцій) гарантовано завершиться за час обмежений функцією з параметром ''k'', але дозвовляє ''маленьку ймовірність помилки''. Зауважте, що будь-який алгоритм Лас-Вегаського типу можна переробити на алгоритм типу Монте-Карло (через [[нерівність Маркова]]), повернувши довільний, можливо неправильний, результат, якщо він не спромігся повернути результат у визначений час. І навпаки, якщо існує дієва процедура перевіряння чи певна відповідь правильна, тоді Монте-Карлівський алгоритм можна обернути на Лас-Вегасівський виконуючи Монте-Карлівський знов і знов допоки не отримали правильну відповідь.
| |||