В теории сложности вычислений принцип Яо или минимаксный принцип Яо гласит, что ожидаемая стоимость вероятностного алгоритма для ввода наихудшего случая не лучше, чем случайное распределение вероятностей наихудшего случайного детерминированного алгоритма, который лучше всего подходит для этого распределения. Таким образом, чтобы установить нижнюю границу производительности вероятностных алгоритмов, достаточно найти подходящее распределение трудных входов и доказать, что ни один детерминированный алгоритм не может хорошо работать против этого распределения. Этот принцип назван в честь Эндрю Яо, который первым предложил его.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .