Пошук порядкової статистики
Пошук порядкової статистики
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-ї порядкової статистики виконує такі кроки:
- Якщо вхідний масив містить лише один елемент, то повернути цей елемент і завершити роботу.
- Всі елементів масиву розбиваються на груп по 5 елементів в кожній і одну групу з елементами (вона може виявитись пустою).
- Кожна група впорядковується методом включення і в кожній з груп обирається медіана.
- Шляхом рекурсивного виклику алгоритму знаходиться медіана множини медіан, знайдених на кроці 3 (якщо медіан дві, то обирається нижня).
- За допомогою модифікованої версії процедури вхідний масив поділяється відносно медіани . Нехай — число на одиницю більше за число елементів що потрапили в першу частину.
- Якщо повертається значення . Інакше, алгоритм викликається рекурсивно, для першої частини, якщо і для другої якщо (при цьому, замінюється на ).
Аналіз роботи[ред. | ред. код]
Час на впорядкування всіх маленьких частин масиву і час на розбиття масиву є O(n). Вибір елемента розбиття x гарантує, що в більшу частину попаде не більше 7n/10+6 елементів. Отже, рівняння для часу роботи є:
Посилання[ред. | ред. код]
- ↑ 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