Попередня Змiст Наступна

5.2. Нижні оцінки складності. Задачі прототипи.

Означення 5.4 Задачі з визначеними оцінками складності, які можна звести до тих, що розглядаються, називаються задачами-прототипами. Вони є базовими для певних класів.
В обчислювальній геометрії використовуються три важливі задачі-прототипи, які мають невелику складність Ω(Nlog N): сортування, визначення крайніх точок та перевірка унікальності елементів множини.
Задача. (УНІКАЛЬНІСТЬ ЕЛЕМЕНТІВ). Задані N дійсних чисел. Визначити, чи існують серед них хоча б два рівних.
Нижня оцінка часової складності для задачі УНІКАЛЬНОСТІ ЕЛЕМЕНТІВ визначається у рамках моделі алгебраїчних дерев розв'язків.
Множину {x1, ..., xN } із N дійсних чисел можна розглядати як точку {x1, ..., xN } в EN. Позначимо через W EN множину істинності для задачі УНІКАЛЬНІСТЬ ЕЛЕМЕНТІВ на множині {x1, ..., xN } (тобто W містить усі точки, будь-яка пара координат яких різна). Стверджується, що W має N компонент зв'язності. Дійсно, будь-якій перестановці p множини {x1, ..., xN } відповідає множина точок у EN.


Зрозуміло, що , по усім p. І при цьому Wπ є компонентами зв'язності, а #(W) = N!.
Таким чином має місце твердження:
Твердження.В рамках моделі алгебраїчних дерев обчислень будь-який алгоритм, який визначає, чи є елементи множини із N дійсних чисел різними, вимагає Ω(Nlog N) перевірок.

Нижні оцінки складності задач на близькість.

1. ПОШУК НАЙБЛИЖЧОГО СУСІДА
ДВІЙКОВИЙ ПОШУК o(1) НАЙБЛИЖЧИЙ СУСІД
Нехай задано N дійсних чисел x1 ,…, xN. У результаті двійкового пошуку визначається число xі, найближче до числа q, яке задається в запиті на пошук.(При цьому допускається попередня обробка). Але цю саму задачу можна подати і в геометричному формулюванні, поставивши у відповідність кожному числу xі точку на площині з координатами (xі, 0). І таким чином пошук найближчого сусіда приведе до тієї ж відповіді, що і двійковий пошук.
Терема 5.2. Для пошуку найближчого сусіда точки в просторі довільної розмірності необхідно виконати Ω(log N) порівнянь (в гіршому випадку).
Якщо, залишаючись в рамках моделі дерев розв'язків, припустити, що число q рівно ймовірно може належати будь-якому із N - 1 інтервалів, які визначаються числами xі, то теорема 5.2 дає оцінку поведінки в середньому для будь-якого алгоритму пошуку найближчого сусіда.

2. k-НАЙБЛИЖЧИХ СУСІДІВ
ПОШУК НАЙБЛИЖЧОГО СУСІДА k-НАЙБЛИЖЧИХ СУСІДІВ.
Що стосується задачі k-НАЙБЛИЖЧИХ СУСІДІВ, то, поклавши k = 1, відразу одержимо зведення ПОШУК НАЙБЛИЖЧОГО СУСІДА k-НАЙБЛИЖЧИХ СУСІДІВ. Таким чином теорема 5.2 застосовується і до задачі k-НАЙБЛИЖЧИХ СУСІДІВ.

3. ЗАДАЧІ Б.1-Б.4.
На малюнку 5.5 показана діаграма звідності задач (на діаграмі символ замінений стрілкою).

5.6


Мал.5.5. Зв'язок задач про близькість з основними задачами, які використовуються як обчислювальні прототипи.
3.1. УНІКАЛЬНІСТЬ ЕЛЕМЕНТІВ N НАЙБЛИЖЧА ПАРА.
Нехай задана множина дійсних чисел { x1 ,…, xN }. Розглядатимемо їх як точки на прямій y = 0, намагаючись знайти найближчу пару точок ({x1 ,..., xN} N { (x1, 0), …, (xN, 0) }). Якщо відстань між точками, які утворюють найближчу пару, не дорівнює нулю, то усі точки множини різні (d = 0 "НІ", d 0 "ТАК"). Так як множину точок, задану в одновимірному просторі, завжди можна вкласти в простір розмірності k, то природно одержується узагальнення цього зведення.
3.2. НАЙБЛИЖЧА ПАРА N УСІ НАЙБЛИЖЧІ СУСІДИ.
Зведення НАЙБЛИЖЧА ПАРА N УСІ НАЙБЛИЖЧІ СУСІДИ очевидне, так як одна із пар, одержаних у результаті розв'язання попередньої задачі, буде найближчою і вона може бути визначена за допомогою О(N) порівнянь.
3.3. НАЙБЛИЖЧА ПАРА N ЕМКД(Б.3).
Так як ЕМКД містить найкоротше ребро евклідового графа на множині із N точок, то задача НАЙБЛИЖЧА ПАРА тривіально зводиться до ЕМКД за лінійний час.
3.4. СОРТУВАННЯ N ЕМКД.
Розглянемо множину із N дійсних чисел {x1 ,…, xN}. Розглядаючи кожне число xі як точку (xі, 0) на площині ({x1 , ..., xN} N { (x1,0),…, (xN,0) }), побудуємо відповідну множину ЕМКД.

ЕМКД: (1,2), (2,3), (3,4), (4,5) (O(N)) (1, 2,3 4, 5,...)

В одержаному ЕМКД вершини, які відповідають числам xі і xj, з'єднані ребром коли xі і xj утворюють пару послідовних чисел у впорядкованій множині. Розв'язком задачі ЕМКД є список, який містить N - 1 пару (i, j), кожна із яких визначає ребро дерева. Не важко перетворити цей список в упорядкований список чисел xі, витративши на це часу О(N).
3.5. СОРТУВАННЯ N ТРІАНГУЛЯЦІЯ(Б.4).
Розглянемо множину із N точок {x1, …, xN}, показану на малюнку 5.6. N-1 точок множини лежать на одній прямій, одна із точок розташована за межами прямої ({x1 ,…, xN} N { (x1, 0),…, (xN-1 , 0), (xN , -a)}). Тріангуляція цієї множини може бути виконана згідно з малюнком єдиним способом. Списком ребер, який породжується алгоритмом тріангуляції, можна скористатись для одержання упорядкованого списку чисел xi, витративши на це додатково О(N) операцій. Таким чином необхідно зробити Ω(Nlog N) порівнянь.


Мал. 5.6. Ілюстрація до одержаної нижньої оцінки складності розв'язання задачі ТРІАНГУЛЯЦІЯ.

Зауваження. Еквівалентне зведення УПОРЯДКОВАНА ОБОЛОНКА N ТРІАНГУЛЯЦІЯ базується на тому, що тріангуляція множини S є планарним графом, зовнішня границя якого є опуклою оболонкою множини S.
Враховуючи, що в рамках моделі дерев обчислень обидві задачі УНІКАЛЬНІСТЬ ЕЛЕМЕНТІВ і СОРТУВАННЯ на множині із N елементів мають нижню оцінку складності Ω(Nlog N), має місце така теорема.
Теорема 5.3У рамках моделі дерев обчислень будь-який алгоритм, який розв'язує одну із задач: НАЙБЛИЖЧА ПАРА, ЕМОД, ТРІАНГУЛЯЦІЯ, УСІ НАЙБЛИЖЧІ СУСІДИ, вимагає Ω(Nlog N) операцій.

Попередня Змiст Наступна