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

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

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