174
правки
Изменения
→Доказательство
=== Доказательство ===
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за <tex>O(N)</tex>. Вероятность, что мы выбрали элемент "удачно" составляет <tex>1 / K</tex>. Тогда, в среднем, мы будем делать <tex>K</tex> шагов. Итоговая сложность <tex>O(N \cdot K)</tex>.
== Источники ==
