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

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

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

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