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