K-я порядковая статистика

Материал из Algocode wiki
Версия от 11:09, 13 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «Пусть дан массив $A$ длиной $N$ и пусть дано число $K$. Задача заключается в том, чтобы найти в...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Пусть дан массив $A$ длиной $N$ и пусть дано число $K$. Задача заключается в том, чтобы найти в этом массиве $K$-ое по величине число, т.е. $K$-ую порядковую статистику.

Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая

1) количество чисел, меньше данного = $k - 1$, тогда наше число - ответ.

2) количество чисел, меньше данного >= $k$, тогда спускаемся рекурсивно в левую часть и ищем там ответ.

3) количество чисел, меньше данного < $k$, спускаемся в правую ищем ($k$ - левая - 1) - ое число.

За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, то есть мы имеем сумму $\sum_{k=1}^n {2 ^ k} = {2^{k+1}-1}$ что в нашем случае это максимум равно $2 * N - 1$, то есть $O(N)$.

Также в с++ эта функция уже реализована :

1 nth_element(указатель на начало, указатель на нужный элемент, указатель на конец);