Порядкова статистика — Вікіпедія

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