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

Лекция №12 курса «Рандомизированные алгоритмы», весна 2021 (Новосибирск). На этой лекции ознакомимся с принципом Яо, который гласит, что ожидаемое время работы рандомизированного алгоритма в худшем случае не меньше, чем ожидаемое время работы наилучшего детерминированного алгоритма на наихудшем распределении на входных данных. Иными словами, для доказательства нижнней оценки трудоёмкости алгоритмов Лас Вегас достаточно найти хотя бы одно распределение случайных входов, на котором все детерминированные алгоритмы в среднем плохо работают. Мы этот принцип используем для доказательства нижних оценок трудоёмкости рандомизированных алгоритмов для упорядочивания массива. Преподаватель курса: Рене Андреасович ван Беверн, заведующий лабораторией алгоритмики ММФ НГУ, старший преподаватель ММФ НГУ. Подробное описание занятия: