K-я порядковая статистика: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 16: | Строка 16: | ||
nth_element(указатель на начало, указатель на нужный элемент, указатель на конец); | nth_element(указатель на начало, указатель на нужный элемент, указатель на конец); | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 20:37, 17 декабря 2019
Пусть дан массив $A$ длиной $N$ и пусть дано число $K$. Задача заключается в том, чтобы найти в этом массиве $K$-ое по величине число, т.е. $K$-ую порядковую статистику.
Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая
1) количество чисел, меньше данного = $k - 1$, тогда наше число - ответ.
2) количество чисел, меньше данного >= $k$, тогда спускаемся рекурсивно в левую часть и ищем там ответ.
3) количество чисел, меньше данного < $k$, спускаемся в правую ищем ($k$ - левая - 1) - ое число.
За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, тогда если мы просуммируем размеры массивов на каждом этапе, мы получим $\sum_{k=0}^n \frac{n}{2 ^ k} = O(n)$.
Также в с++ эта функция уже реализована :
1 nth_element(указатель на начало, указатель на нужный элемент, указатель на конец);
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin