Шервудские алгоритмы.

Шервудские алгоритмы всегда возвращают ответ, и этот ответ всегда правильный. Эти алгоритмы применимы в ситуациях, когда различие между наилучшим, средним и наихудшим случаями в детерминированном алгоритме очень велико. Применение случайности позволяет шервудским алгоритмам сократить спектр возможностей, подтянув наихудший и наилучший случаи к среднему.

Этот подход можно применять и в задаче поиска. При двоичном поиске прежде, чем добраться до некоторых элементов списка, мы должны с необходимостью совершить несколько неудачных проверок. Шервудский вариант «двоичного» поиска выбирает случайный элемент между началом и концом списка и сравнивает его с искомым.

Иногда оставшийся кусок оказывается меньше, чем тот, что мы бы получили при настоящем двоичном поиске, а иногда — больше. Так, например, не исключено, что в списке из 400 элементов мы выберем для пробного сравнения не 200-ый, а сотый. Если искомый элемент находится среди первых ста, то наша шервудская версия алгоритма поиска позволяет отбросить 75% списка вместо 50% в стандартном алгоритме. Однако если интересующий нас элемент больше сотого, то отброшенными окажутся лишь 25% списка. Вновь в некоторых случаях мы получаем выигрыш, а иногда проигрываем.

Как правило, шервудские алгоритмы уменьшают время обработки наихудшего случая, однако увеличивают время обработки наилучшего.

Подобно Робин Гуду из Шервудского леса этот подход грабит богатых, чтобы отдать бедным.