wiki2.red

Принцип Яо

Материал из Википедии — свободной энциклопедии

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

Литература

Ссылки

Что такое wiki2.red Вики является главным информационным ресурсом в интернете. Она открыта для любого пользователя. Вики это библиотека, которая является общественной и многоязычной.

Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License.

Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. wiki2.red является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).

E-mail: ivanovalik@yahoo.com