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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Названий на честь своїх винахідників: Manual B lum, Robert W. F loyd, Vaughan R. P ratt, Ronald L. R ivest і Robert Endre T arjan. Також відомий англійський як median-of-medians algorithm

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

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

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

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