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

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

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)}$ в середньому і навіть у найгіршому випадках.

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

Досі невідомо, скільки саме порівнянь необхідно зробити для пошуку медіани. Нижня границя, рівна 2n порівнянням, була знайдена Бентом і Джоном ^[4], а верхня границя, рівна 3n порівнянням, — Шйонхагом, Патерсоном і Піппенджером^[5]. Дор і Цвік^[6] покращили обидві границі; їх верхня границя трохи менша за 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})}$

Названий в честь своїх винахідників: 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. ISBN 0-07-013151-1