K-я порядковая статистика: различия между версиями

Версия 20:31, 17 декабря 2019

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

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

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

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

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

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

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

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

@@ Строка 9: / Строка 9: @@
 ) количество чисел, меньше данного < $k$, спускаемся в правую ищем ($k$ - левая - 1) - ое число.
-За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, то есть мы имеем сумму $\sum_{k=1}^n {2 ^ k} = {2^{k+1}-1}$ что в нашем случае это максимум равно $2 * N - 1$, то есть $O(N)$.
+За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, тогда если мы просуммируем размеры массивов на каждом этапе, мы получим $\sum_{k=1}^n \frac{n}{2 ^ k} = O(n)$.
 Также в с++ эта функция уже реализована :