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

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

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

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

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

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

Дано: множину , що складається з (різних) чісел , і число

Потрібно знайти: елемент , що більший за рівно інших елементів множини

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

Історія

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

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

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

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

Псевдокод


1. 
2. 
3. 
4. if 
5.    then if 
6.            then 
7.            else 
8.         
9. while 
10.      do 
11.         
12.         if 
13.            then Поміняти 
14.         if 
15.            then 
16.         if 
17.            then 
18.         

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

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

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

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

Псевдокод

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


1 
2 
3 for  to  
4 do  if 
5     then 
6          Поміняти 
7 
8 Поміняти 
9 return 

Функція Робить те ж саме, але вносить рандомізацію в поділ.


1 
2 Поміняти 
9 return 

Сам пошук k-ої статистики в масиві A здійснюється функцією


1. if 
2.    then return 
3. 
4. 
5. if 
6.    then return 
7. elseif 
8.    then return 
9.    else return 

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

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

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

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

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

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

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

  1. Якщо вхідний масив містить лише один елемент, то повернути цей елемент і завершити роботу.
  2. Всі елементів масиву розбиваються на груп по 5 елементів в кожній і одну групу з елементами (вона може виявитись пустою).
  3. Кожна група впорядковується методом включення і в кожній з груп обирається медіана.
  4. Шляхом рекурсивного виклику алгоритму знаходиться медіана множини медіан, знайдених на кроці 3 (якщо медіан дві, то обирається нижня).
  5. За допомогою модифікованої версії процедури вхідний масив поділяється відносно медіани . Нехай — число на одиницю більше за число елементів що потрапили в першу частину.
  6. Якщо повертається значення . Інакше, алгоритм викликається рекурсивно, для першої частини, якщо і для другої якщо (при цьому, замінюється на ).

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

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

Посилання

  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