Порядкова статистика

Хай маємо множину (масив) з n чисел.

i-та порядкова статистика, це елемент, який буде i-тим за рахунком в масиві, якщо його елементи відсортувати в порядку зростання.

Тоді, наприклад мінімум — це перша порядкова статистика, а максимум — n-та порядкова статистика.

Медіана — елемент, який знаходиться точно посередині між мінімумом і максимумом. Якщо говорити точніше, то якщо n — непарне, то медіана — (n+1)/2-га порядкова статистика, а якщо n — парне, то медіан аж дві: з номером n/2 і n/2+1.

Пошук і-тої порядкової статистики

Найочевидніше, і найпростіше рішення — відсортувати масив, і після цього будь-яку порядкову статистику можна знаходити за одиничний час. Це хороше рішення, якщо нам потрібно шукати багато різних статистик одного масиву. Правда сортування масиву займає час мінімум O(n log(n)).

З усім тим, в багатьох задачах порядкову статистику потрібно знайти лише раз. І це можна зробити за лінійний час. Пошук мінімуму або максимуму — тривіальна задача:

 int min(int *a, int l, int r)
 {
      int m=l;
      for(int i=l+1;i<=r;i++)
      {
          if(a[i]<a[m]) m=i;
      }
      return a[m];
 }

Але не сортуючи масив можна знайти й будь-яку іншу порядкову статистику. Секрет в тому, що масив сортується, але не повністю. Розглянемо швидке сортування.

 void qsort(int *a, int l, int r)
 {
       if(l>=r) return;
       int c=partition(int *a, int l, int r);
       qsort(a,l,c);
       qsort(a,c+1,r);
 }

Спочатку масив ділять на дві частини, де всі елементи лівої частини менші за будь-який з правої. Ми знаємо, що в лівій частині c елементів. Тому, якщо i — номер елемента якого ми шукаємо, то він знаходиться в лівій частині, якщо ${\displaystyle i\leq c}$ інакше він знаходиться в правій частині, але при пошуку в правій частині не забуваємо, що зліва є c менших елементів. Спробуємо написати функцію пошуку порядкової статистики використавши ці міркування:

 int nth_element(int *a, int l, int r, int n)
 {
       if(l=r) return a[l];
       int c=partition(int *a, int l, int r);
       int k=c-l+1;
       if(n<=k) return nth_element(a,l,c,n);
       else return nth_element(a,c+1,r, n-k);
 }

Функція partition розглянута тут. Вона працює за час O(r-l). Позначимо розмір частини яка обробляється змінною s. (s=r-l). В ідеалі, при кожному вході в рекурсію s зменшується вдвоє. Тому загальний час роботи O(s+s/2+s/4+s/8+…)=O(2s)=O(s), тобто лінійний. Така оцінка є середньою. Тобто час може бути й гіршим. Існує алгоритм, для якого лінійний час є найгіршим.