Изменения

Этот алгоритм почти ни чем не отличается от алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]], но имеет важное отличие в том, что время работы алгоритма в наихудшем случае <tex>O(n)</tex>, где <tex>n</tex> количество элементовв множестве. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\frac{3n}{10}</tex>. Элементов же больших опорного элемента, также не менее <tex>\frac{3n}{10}</tex>,. Благодаря этому алгоритм работает за линейной время в любом случае.

Проведем анализ рассекающего элемента. На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по <tex> 8 </tex> элементов, всего же в массиве <tex> 25 </tex>, то есть мы получили хорошее (то есть соответствующее нашему утверждению) разбиение массива относительно опорного элемента, так как <tex> 8 > </tex> <tex>\frac{3 \cdot 25}{10}</tex>. Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и в общем случае. Доказательство представлено ниже Cначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент <tex>x</tex>. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан <tex>x</tex>. Таким образом, как минимум <tex>n</tex> <tex>/</tex> <tex>10</tex> групп содержат по <tex>3</tex> превышающих величину <tex>x</tex>, за исключение группы, в которой меньше <tex>5</tex> элементов и ещё одной группы, содержащей сам элемент <tex>x</tex>. Таким образом получаем, что количество элементов больших <tex>x</tex>, не менее <tex>\frac{3n}{10}</tex>. Проведя аналогичные рассуждения для элементов, которые меньше по величине, чем рассекающий элемент <tex>x</tex>, мы получим, что как минимум <tex>\frac{3n}{10}</tex> меньше, чем элемент <tex>x</tex>. Теперь проведем анализ времени работы алгоритма.