13
правок
Изменения
Нет описания правки
На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за <tex>O(N)</tex>. Вероятность, что мы выбрали элемент "удачно" составляет <tex>1 / K</tex>. Тогда, в среднем, мы будем делать <tex>K</tex> проверок. Итоговая сложность <tex>O(N \cdot K)</tex>.
== Источники информации==
* [http://habrahabr.ru/post/167177/ Habrahabr - Поиск часто встречающихся элементов в массиве]
