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

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

i-ю порядковою статистикою (англ. order statistic) множини з n елементів називається i-й у порядку зростання елемент множини.

Так мінімум множини — це перша порядкова статистика, а максимум — n-та порядкова статистика. Медіа́на (англ. median) неформально означає середину множини. Якщо n непарне, то медіана єдина, і її індекс (індекс відповідної порядкової статистики) дорівнює i = (n + 1) / 2; якщо ж n парне, то медіани дві: i = n / 2 та i = n / 2 + 1.

Формально задача пошуку порядкової статистики визначається так:

Дано: множину$\;A$, що складається з$\;n$ (різних) чисел, і число $1\leq i\leq n$

Потрібно знайти: елемент $x\in A$, що більший за рівно$\;i-1$ інших елементів множини$\;A$.

Задачу можна розв'язати за час$\;O(n\log n)$. Для цього достатньо впорядкувати елементи за зростанням, а потім взяти i-й елемент. Але є алгоритми що можуть розв'язати цю задачу за час$\;O(n)$ в середньому і навіть у найгіршому випадках.

Історія

Алгоритм пошуку медіан, час роботи якого в найгіршому випадку лінійно залежить від кількості вхідних елементів, був розроблений Блюмом, Флойдом, Праттом, Рівестом і Таржаном. Версія цього алгоритму зі зниженим середнім часом роботи була опублікована в роботі Тоні Гоара. Флойд і Рівест створили покращену версію алгоритму, що працювала в середньому ще краще.

Досі невідомо, скільки саме порівнянь необхідно зробити для пошуку медіани. Нижня границя, рівна 2n порівнянням, була знайдена Бентом і Джоном , а верхня границя, рівна 3n порівнянням, — Шйонхагом, Патерсоном і Піппенджером. Дор і Цвік покращили обидві границі; їх верхня границя трохи менша за 2,95n, а нижня — трохи більша за 2n.

Алгоритм пошуку мінімуму та максимуму

Окремо мінімум і максимум (першу і n-ну порядкові статистики) множини (масиву) можна знайти за$\;n-1$ порівнянь кожен. У практичних задачах часто необхідно одночасно знайти і мінімум, і максимум. при одночасному пошуку кількість порівнянь можна зменшити з $\;2n-2$ до $3\lfloor n/2\rfloor$ порівнянь. Для цього потрібно брати по два елементи з множини і порівнювати їх між собою. Потім більший елемент порівнювати з поточним максимумом, а менший — з поточним мінімумом. Таким чином, економиться 1 порівняння (3 порівняння замість 4).

Псевдокод

$\;FindMaxMin(A)$
1. $min\leftarrow A[1]$
2. $max\leftarrow A[1]$
3. $i\leftarrow 2$
4. if $\;length[A]\mod 2=0$
5.    then if $\;A[2]>max$
6.            then $max\leftarrow A[2]$
7.            else $min\leftarrow A[2]$
8.         $i\leftarrow 3$
9. while $i\leq length[A]$
10.      do $j\leftarrow i$
11.         $k\leftarrow i+1$
12.         if $\;A[j]>A[k]$
13.            then Поміняти $j\leftrightarrow k$
14.         if $A[j]<min\;$
15.            then $min\leftarrow A[j]$
16.         if $A[k]>max\;$
17.            then $max\leftarrow A[k]$
18.         $i\leftarrow i+2$

Така оптимізація доцільна у випадках, коли порівняння елементів з множини A займає багато часу. Наприклад, якщо порівнюється текст або графічні зображення.

Алгоритм пошуку за лінійний в середньому час

Алгоритм ґрунтується на принципі "розділяй і владарюй", і працює подібно до швидкого сортування. Для забезпечення малого часу роботи для всіх можливих вхідних даних, в алгоритм уводиться рандомізація. Алгоритм запропонував Тоні Гоар

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

Псевдокод

Функція $Partition(A,p,q)$ виконує розділення частини масиву з p-го по q-й елемент на дві менші частини.

$Partition(A,p,q)\;$
1 $x\gets \;A[q]$
2 $i\gets \;p-1$
3 for $j\gets \;p$ to $\;q-1$ 
4 do  if $A[j]\leq \;x\;$
5     then $i\gets \;i+1$
6          Поміняти $A[i]\leftrightarrow \;A[j]$
7 $i\gets \;i+1$
8 Поміняти $A[i]\leftrightarrow \;A[q]$
9 return $\;i$

Функція $Randomized\_Partition(A,p,q)$ Робить те ж саме, але вносить рандомізацію в поділ.

$Randomized\_Partition(A,p,q)\;$
1 $i\leftarrow Random(p,q)$
2 Поміняти $A[i]\leftrightarrow A[q]$
9 return $\;Partition(A,p,q)$

Сам пошук k-ї статистики в масиві A здійснюється функцією $Randomized\_Select(A,1,length[A],k)$

$Randomized\_Select(A,p,q,k)\;$
1. if $\;p=q$
2.    then return $\;A[p]$
3. $r\leftarrow Randomized\_Partition(A,p,q)$
4. $t\leftarrow r-p+1$
5. if $\;k=t$
6.    then return $\;A[r]$
7. elseif $\;k<t$
8.    then return $\;Randomized\_Select(A,p,r-1,k)$
9.    else return $\;Randomized\_Select(A,r+1,q,k-t)$

Аналіз алгоритму

В найкращому випадку (за умови розбиття на рівні частини), час роботи пошуку описується рівнянням:

$\;T(n)=T\left({\frac {n}{2}}\right)+O(n)=O(n)$

Середній час роботи також є$\;O(n)$, і завдяки рандомізації швидкість роботи на довільному вході близька до середньої. Якщо ж розбиття вибрано погано то в найгіршому випадку складність буде $\;O(n^{2})$

Алгоритм пошуку за лінійний час (BFPRT-алгоритм)

Названий в честь своїх винахідників: Manual Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest і Robert Endre Tarjan. Також відомий англійською як median-of-medians algorithm

Алгоритм працює подібно до попереднього, але він гарантує собі хороше розбиття, а отже і час роботи в найгіршому випадку O(n).

Алгоритм пошуку k-ї порядкової статистики виконує такі кроки:

1. Якщо вхідний масив містить лише один елемент, то повернути цей елемент і завершити роботу.
2. Всі $\;n$ елементів масиву розбиваються на $\lfloor n/5\rfloor$ груп по 5 елементів в кожній і одну групу з $\;n\mod 5$ елементами (вона може виявитись пустою).
3. Кожна група впорядковується методом включення і в кожній з груп обирається медіана.
4. Шляхом рекурсивного виклику алгоритму знаходиться медіана $\;x$ множини $\lceil n/5\rceil$ медіан, знайдених на кроці 3 (якщо медіан дві, то обирається нижня).
5. За допомогою модифікованої версії процедури $\;Partition$ вхідний масив поділяється відносно медіани $\;x$. Нехай $\;i$ — число на одиницю більше за число елементів що потрапили в першу частину.
6. Якщо $\;k=i$ повертається значення $\;x$. Інакше, алгоритм викликається рекурсивно, для першої частини, якщо $\;k<i$ і для другої якщо $\;k>i$ (при цьому, $\;k$ замінюється на $\;k-i$).

Аналіз роботи

Час на впорядкування всіх маленьких частин масиву і час на розбиття масиву є O(n). Вибір елемента розбиття x гарантує, що в більшу частину попаде не більше 7n/10+6 елементів. Отже, рівняння для часу роботи є:

$T(n)=T\left(\left\lceil {\frac {n}{5}}\right\rceil \right)+T\left({\frac {7n}{10}}+6\right)+O(n)=O(n)$

Джерела

• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1