City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Нижние оценки трудоёмкости рандомизированных алгоритмов — принцип Яо
Randomized Algorithms

What: Lecture
When: Wednesday, 12 May 2021, 18:10–19:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

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