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

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

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

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

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

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

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

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

Історія

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

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

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

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

Псевдокод

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

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

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

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

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

Псевдокод

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

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

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

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

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

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

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

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

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

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

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

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

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

Посилання

1. Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest and Robert E. Tarjan. Time Bounds for Selection. Journal of Computer and System Sciences, 7(4):448-461, 1973
2. C.A.R. Hoare. Algorithm 63 (PARTITION) and Algorithm 65 (FIND). Communications of the ACM, 4(7):321-322, 1961
3. Robert W. Floyd and Ronald L. Rivest. Expected Time Bounds for Selection. Communications of the ACM, 18(3):165-172, 1975
4. Samuel W. Bent and John W. John. Finding the Median Requires 2n Comparisons. In Proceedings of the 41st Annual Symposium on Fundations of Computer Science, pages 399-409, 2000
5. A. Schönhage, M. Paterson and N. Pippenger. Finding the median. Journal of Computer and System Sciences, 13(2):184-199, 1976
6. Dorit Dor and Uri Zwick. Selecting the Median. In Preceeding of the 6th ACM-SIAM Symposium on Descrete Algorithms, pages 28-37, 1995

Джерела

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