Хай маємо множину масив з n чисел i та порядкова статистика це елемент який буде i тим за рахунком в масиві якщо його ел

Хай маємо множину (масив) з 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 — номер елемента якого ми шукаємо, то він знаходиться в лівій частині, якщо $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), тобто лінійний. Така оцінка є середньою. Тобто час може бути й гіршим. Існує алгоритм, для якого лінійний час є найгіршим.