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