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

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

i-ю порядковою статистикою (Шаблон:Lang-en) множини з n елементів називається i-й у порядку зростання елемент множини.

Так мінімум множини — це перша порядкова статистика, а максимум — n-та порядкова статистика. Медіа́на (Шаблон:Lang-en) неформально означає середину множини. Якщо 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)$ в середньому і навіть у найгіршому випадках.

Історія

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

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

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

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

Псевдокод

 $F i n d M a x M i n (A)$ 
1.  $m i n \leftarrow A [1]$ 
2.  $m a x \leftarrow A [1]$ 
3.  $i \leftarrow 2$ 
4. if  $l e n g t h [A] mod 2 = 0$ 
5.    then if  $A [2] > m a x$ 
6.            then  $m a x \leftarrow A [2]$ 
7.            else  $m i n \leftarrow A [2]$ 
8.          $i \leftarrow 3$ 
9. while  $i \leq l e n g t h [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] < m i n$ 
15.            then  $m i n \leftarrow A [j]$ 
16.         if  $A [k] > m a x$ 
17.            then  $m a x \leftarrow A [k]$ 
18.          $i \leftarrow i + 2$

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

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

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

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

Псевдокод

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

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

Функція $R a n d o m i z e d_P a r t i t i o n (A, p, q)$ Робить те ж саме, але вносить рандомізацію в поділ.

 $R a n d o m i z e d_P a r t i t i o n (A, p, q)$ 
1  $i \leftarrow R a n d o m (p, q)$ 
2 Поміняти  $A [i] \leftrightarrow A [q]$ 
9 return  $P a r t i t i o n (A, p, q)$

Сам пошук k-ї статистики в масиві A здійснюється функцією $R a n d o m i z e d_S e l e c t (A, 1, l e n g t h [A], k)$

 $R a n d o m i z e d_S e l e c t (A, p, q, k)$ 
1. if  $p = q$ 
2.    then return  $A [p]$ 
3.  $r \leftarrow R a n d o m i z e d_P a r t i t i o n (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  $R a n d o m i z e d_S e l e c t (A, p, r - 1, k)$ 
9.    else return  $R a n d o m i z e d_S e l e c t (A, r + 1, q, k - t)$

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

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

$T (n) = T (\frac{n}{2}) + 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-ї порядкової статистики виконує такі кроки:

Якщо вхідний масив містить лише один елемент, то повернути цей елемент і завершити роботу.
Всі $n$ елементів масиву розбиваються на $⌊ n / 5 ⌋$ груп по 5 елементів в кожній і одну групу з $n mod 5$ елементами (вона може виявитись пустою).
Кожна група впорядковується методом включення і в кожній з груп обирається медіана.
Шляхом рекурсивного виклику алгоритму знаходиться медіана $x$ множини $⌈ n / 5 ⌉$ медіан, знайдених на кроці 3 (якщо медіан дві, то обирається нижня).
За допомогою модифікованої версії процедури $P a r t i t i o n$ вхідний масив поділяється відносно медіани $x$ . Нехай $i$ — число на одиницю більше за число елементів що потрапили в першу частину.
Якщо $k = i$ повертається значення $x$ . Інакше, алгоритм викликається рекурсивно, для першої частини, якщо $k < i$ і для другої якщо $k > i$ (при цьому, $k$ замінюється на $k - i$ ).

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

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

$T (n) = T (⌈ \frac{n}{5} ⌉) + T (\frac{7 n}{10} + 6) + O (n) = O (n)$

Посилання

↑ 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
↑ C.A.R. Hoare. Algorithm 63 (PARTITION) and Algorithm 65 (FIND). Communications of the ACM, 4(7):321-322, 1961
↑ Robert W. Floyd and Ronald L. Rivest. Expected Time Bounds for Selection. Communications of the ACM, 18(3):165-172, 1975
↑ 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
↑ A. Schönhage, M. Paterson and N. Pippenger. Finding the median. Journal of Computer and System Sciences, 13(2):184-199, 1976
↑ 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

[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

[1]

[2]

[3]

[4]

[5]

[6]

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

Зміст

Історія

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

Псевдокод

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

Псевдокод

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

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

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

Посилання

Джерела

Навігаційне меню