Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

K-порядковая статистика (или K-й порядковый элемент) - это алгоритм, который находит $k$-й элемент в отсортированной версии массива, не сортируя весь массив.

---

Сферы применения

K-порядковая статистика находит свое применение в задачах, где требуется быстро определить $k$-й элемент по величине в массиве, не прибегая к полной сортировке. Это делает алгоритм особенно полезным в ситуациях, где важен быстрый доступ к данным и их анализ.

• Медиана: часто используется для нахождения медианы в массиве, особенно в задачах, связанных с анализом данных.
• Квантили: применяется для поиска различных квантилей (например, $25$-й или $75$-й перцентиль) в статистике. Квантили — это статистические меры, которые делят данные на равные части. Например, медиана — это $50$-й перцентиль или $0.5$-квантиль, которая делит данные на две равные части. Квантили позволяют понять распределение данных и найти значения, которые отделяют определенные доли набора данных.
• Поиск элементов: подходит для поиска $k$-й по величине или $k$-й по порядку элемента в больших наборах данных.

---

Принцип работы алгоритма

Алгоритм $k$-порядковой статистики использует принцип "разделяй и властвуй", аналогичный быстрой сортировке (QuickSort). Весь процесс делится на несколько шагов, которые позволяют эффективно найти $k$-й элемент без полной сортировки массива.

Шаги алгоритма

1. Выбираем опорный элемент из списка.

2. Разделяем список на три части:

   1. Левая часть содержит все элементы, которые меньше опорного.
   2. Правая часть содержит все элементы, которые больше опорного.
   3. Средняя часть содержит все элементы, которые равны опорному.

3. Сравниваем значение $k$ с размерами левой и средней частей:

   1. Если $k$ меньше размера левой части, то искомая $k$-порядковая статистика находится в левой части, и рекурсивно запускаем наш алгоритм для левой части.
   2. Если $k$ больше размера левой и средней частей, то искомая $k$-порядковая статистика находится в правой части, и мы рекурсивно запускаем наш алгоритм для правой части. При этом, уменьшаем $k$ на сумму длин левой и средней частей, из-за смещения индексов.
   3. Если $k$ находится между размерами левой и средней частей, то опорный элемент является искомой k-порядковой статистикой, и возвращаем его значение.

4. Продолжаем рекурсивно делить исходный список и выбирать опорный элемент, пока k-порядковая статистика не будет найдена.

---

Особенности

• Быстрее полной сортировки: в большинстве случаев выполняется быстрее, чем сортировка всего массива.
• Простота реализации: относительно простой в реализации и понимании.
• Универсальность: может быть использован для поиска любого $k$-го элемента в массиве.
• Неустойчивость к худшему случаю: в худшем случае может работать медленно, особенно если опорный элемент выбирается неудачно.
• Зависимость от выбора опорного элемента: эффективность сильно зависит от удачного выбора опорного элемента.

---

Вычислительная сложность

Средний случай

В среднем случае вычислительная сложность алгоритма составляет $O(n)$. Это достигается благодаря тому, что опорный элемент (pivot) в среднем делит массив на достаточно равные части, что позволяет алгоритму быстрее находить нужный элемент без полного обхода массива.

Доказательство

• Равномерное разбиение: предположим, что в среднем случае опорный элемент делит массив примерно на две равные части. То есть, каждый раз массив делится на две части размером $\frac{n}{2}$​.

• Рекурсивное уравнение: для оценки средней сложности можем записать следующее рекурсивное уравнение:

$\huge T(n) = T\left(\frac{n}{2}\right) + O(n)$ Здесь:

• $T\left(\frac{n}{2}\right)$ — сложность вызова алгоритма на половине массива.

• $O(n)$ — время, необходимое для разбиения массива и поиска порядка элемента.

• Решение уравнения: это уравнение можно решить методом разложения (Master Theorem):

  $\huge T(n) = O(n) + O\left(\frac{n}{2}\right) + O\left(\frac{n}{4}\right) + ... + O(1)$

  Сумма геометрической прогрессии:

$\huge T(n) = n \left(1 + \frac{1}{2} + \frac{1}{4} + \ldots\right)$

• Сходимость прогрессии: Сумма этой геометрической прогрессии равна:

$\huge T(n) = n \cdot \sum_{k=0}^{\infty} \left(\frac{1}{2}\right)^k = n \cdot 2 = O(n)$

Таким образом, средняя вычислительная сложность поиска $k$-й порядковой статистики составляет $O(n)$. Это достигается за счет эффективного разбиения массива опорным элементом, что позволяет сократить количество элементов для последующих рекурсивных вызовов.

Худший случай

В худшем случае вычислительная сложность алгоритма составляет $O(n^2)$. Это происходит, когда опорный элемент (pivot) каждый раз выбирается так, что он оказывается либо минимальным, либо максимальным элементом текущего подмассива. В результате массив разделяется на части размером $1$ и $n-1$, что приводит к наибольшему количеству рекурсивных вызовов.

Доказательство

• Выбор опорного элемента: в худшем случае на каждом этапе опорный элемент делит массив на части размером $0$ и $n-1$. Это происходит, когда опорный элемент всегда оказывается самым большим или самым маленьким элементом подмассива.

• Рекурсивный процесс: из-за неудачного выбора опорного элемента алгоритм вынужден обрабатывать все $n-1$ элементов в каждой рекурсии, затем $n-2$ элементов, и так далее. В результате количество операций, необходимых для обработки каждого уровня, составляет $O(n)$.

• Общее количество операций: поскольку количество операций на каждом уровне составляет $O(n)$, а число уровней в худшем случае — $n$, общее количество операций равно:

$\huge T(n) = n + (n-1) + (n-2) + ... + 1$

• Сумма арифметической прогрессии: эта сумма представляет собой арифметическую прогрессию, которая может быть записана как:

  $\huge T(n) = \frac{n(n+1)}{2}$

  Опуская константы и младшие члены, сложность составляет $O(n^2)$.

Таким образом, в худшем случае, когда опорный элемент всегда делит массив на максимально неравные части, алгоритм имеет вычислительную сложность $O(n^2)$.

---

Пространственная сложность

Средний и худший случай: $O(1)$. Алгоритм работает на месте, не требуя дополнительной памяти пропорциональной размеру входных данных, кроме стека вызовов в рекурсивной версии.

Доказательство

Поскольку алгоритм работает на месте (in-place) и использует только константное количество дополнительной памяти, его пространственная сложность составляет $O(1)$. Стек вызовов для рекурсивной версии требует $O(\log (n))$ в среднем и $O(n)$ в худшем случае, но это всё равно меньше, чем $O(n)$ для хранения дополнительных данных.

---

Схематическая работа алгоритма

Исходный массив :

Предположим, мы ищем $4$-й порядковый элемент (то есть $4$-й по величине элемент).

Шаг 1:

Выберем в исходном массиве опорным элементом центральное число - $10$

Разделим исходный массив на $3$ подмассива: меньше, равные и больше

Шаг 2:

• В "меньших" три элемента.
• В "равных" два элемента. Итого, $3 + 2 = 5$ элементов, так что $8$-й элемент находится в "больших".

Теперь ищем $8$-й элемент минус $5$ элементов в первых двух группах, то есть $3$-й элемент среди оставшихся.

Шаг 3:

Теперь мы ищем $3$-й порядковый элемент среди массива. Выбираем опорным элементом $19$ и разделяем массив на три подмассива.

Теперь ищем $3$-й элемент:

• Меньших элементов нет.
• Равные — это $1$-й элемент, так что мы ищем $2$-й элемент в массиве $[30, 20, 81]$.

Шаг 4

Теперь мы ищем $2$-й элемент среди:

Выбираем опорным элементом $20$ и разделяем массив на три подмассива: меньше, равные и больше.

Равные — это $1$-й элемент, так что $2$-й элемент — это первый элемент из "больших", то есть $30$.

Результат

$8$-я порядковая статистика для массива — это $30$.

---

Псевдокод

функция k_порядковая_статистика(массив, k): 
    если длина(массив) == 1:  
        вернуть массив[0]  

    опорный_элемент = массив[длина(массив) // 2]  
    левый = [x для x в массив если x < опорный_элемент]
    правый = [x для x в массив если x > опорный_элемент]
    равные = [x для x в массив если x == опорный_элемент]

    если k < длина(левый):  
        вернуть k_порядковая_статистика(левый, k)  

    иначе если k < длина(левый) + длина(равные): 
        вернуть равные[0]  
  
    иначе:  
        вернуть k_порядковая_статистика(правый, k - длина(левый) - длина(равные))

---

Реализация на Python

Аннотация:
k_order_statistic - функция K-порядковой статистики
arr - массив, в котором происходит поиск
k - искомая статистика
pivot - опорный элемент
left - массив с элементами, которые меньше опорного
right - массив с элементами, которые больше опорного
equal - массив с элементами, которые равны опорному

def k_order_statistic(arr, k): 
    if len(arr) == 1:  
        return arr[0]  

    pivot = arr[len(arr) // 2]  
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x > pivot]
    equal = [x for x in arr if x == pivot]

    if k < len(left):  
        return k_order_statistic(left, k)  

    elif k < len(left) + len(equal): 
        return equal[0]  
  
    else:  
        return k_order_statistic(right, k - len(left) - len(equal))

---

Олимпиадная реализация на C++

Аннотация:
typedef - переопределение имени типа данных
kOrder - функция K-порядковой статистики
arr - массив, в котором происходит поиск
k - искомая статистика
p - опорный элемент
l - массив с элементами, которые меньше опорного
r - массив с элементами, которые больше опорного
equ - массив с элементами, которые равны опорному

typedef vector<int> vi;
int kOrder(vi& arr, int k) {
  if (arr.size() == 1) return arr[0];
  int p = arr[arr.size() / 2];
  std::vector<int> l, r, equ;
  for (int x : arr) {
    if (x < p)
      l.push_back(x);
    else if (x > p)
      r.push_back(x);
    else
      equ.push_back(x);
  }
  if (k < l.size())
    return kOrder(l, k);
  else if (k < l.size() + equ.size())
    return equ[0];
  else
    return kOrder(r, k - l.size() - equ.size());
}

---

Продуктовая реализация на C++

Аннотация:
kOrderStatistic - функция K-порядковой статистики
array - массив, в котором происходит поиск
k - искомая статистика
pivot - опорный элемент
left - массив с элементами, которые меньше опорного
right - массив с элементами, которые больше опорного
equal - массив с элементами, которые равны опорному

int kOrderStatistic(std::vector<int>& array, int k) {
  if (array.size() == 1) return array[0];

  int pivot = array[array.size() / 2];
  std::vector<int> left, right, equal;

  for (int element : array) {
    if (element < pivot)
      left.push_back(element);
      
    else if (element > pivot)
      right.push_back(element);
      
    else
      equal.push_back(element);
  }

  if (k < left.size())
    return kOrderStatistic(left, k);

  else if (k < left.size() + equal.size())
    return equal[0];

  else
    return kOrderStatistic(right, k - left.size() - equal.size());
}