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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

Дано: множину \;A, що складається з \;n (різних) чісел , і число 1 \le i \le 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 порівнянь кожен. В практичних задачах часто необхідно одночасно знайти і мінімум і максимум. при одночасному пошуку кількість порівнянь можна зменшити з \;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 \le 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]\le\;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)

Посилання[ред.ред. код]

  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