Вероятностные алгоритмы отличаются от обычных тем, что в них используется генератор случайных чисел. 24

Для обычных алгоритмов время работы на каждом наборе входных данных — это одно число: количество шагов в проделанном вычислении, однозначно определённое. 4 Для вероятностных алгоритмов на каждом наборе входных данных возможно несколько вычислений — в зависимости от того, какие случайные числа будут получены, вычисление пойдёт одним или другим путём. 4 Для каждого из этих вычислений определена вероятность того, что произойдёт именно оно. 4

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

Однако при включении метода генерации случайных чисел в список «исходных данных» вероятностный алгоритм становится подвидом обычного. 1