Algoritmy_i_struktury_dannykh - Стор 6
02: container: binarySearchTree
05: Insert Impl (D, key, value)
07: Insert(container, key, value) 08:
09: Delete Impl (D, key)
11: Delete (container, key) 12:
13: Look Up Impl (D, key)
15: return Search(container, key)
Таким чином, трудомісткість операцій вставки, видалення та пошуку безпосередньо залежить від трудомісткості виконання відповідних операцій над структурою даних, що лежить в основі словника. Зазначимо, що з використанні хеш-таблиц безліч ключів необов'язково лінійно впорядковане безліч (т. е. таке, коли елементи можна порівняти між собою), тоді як більшість деревоподібних структур даних ця умова є необхідним.
Словникові структури даних знаходять широке використання практично. Як приклад може бути застосування словникових структур даних до так званої техніки мемоізації * у тих завдань, розв'язуваних з допомогою методу динамічного програмування.
Розглянемо деяку абстрактну обчислювальну задачу , яка може бути вирішена методом динамічного програмування, шляхом розбі-
ня вихідного завдання на дрібніші підзадачі
таких підзавдань. Припустимо, що кожному завданню
стан, що описує завдання. Також виділимо ряд елементарних завдань, для яких рішення відоме. Стани, що відповідають елементарним завданням, назвемо початковими . Зв'язавши всі стани в деякий ациклічний граф можна запропонувати наступний спосіб знаходження рішення задачі , якій відповідає стан (процедура 2.3.11):
* Термін мемоізація походить від англійського memoization.
Процедура 2.3.11: Memoization Technique
01: Calculate Impl (S)
02: ifno Contains(cache, S) then
foreach S і в Adjacency List(G, S) do
accumulate(result, Calculate(S i ))
07: return cache[S]
Трудомісткість даного алгоритму є , де число станів, а число переходів у графі , за умови, що функція накопичення результату працює за константний час.
Як можна бачити з наведеного алгоритму, як кеш має бути використана така словникова структура даних, яка дозволить ефективно здійснювати вставку та пошук елемента. Якщо стану можна занумерувати натуральними числами, то як кеш може бути використаний масив. Перед безпосереднім викликом процедури обчислення до словника повинні бути розміщені елементарні стани разом з обчисленими для них значеннями. Щоб відповісти питанням, чому дана техніка дає відчутний виграш, розглянемо завдання визначення кількості шляхів, які ведуть з вершини на вершину , наступного графі (рис. 2.5):
Якщо обчислення шляхів вести безпосередньо, кількість кроків буде порівняно з ). Скориставшись технікою мемоізації, трудомісткість алгоритму можна значно зменшити. У цьому випадку достатньо запам'ятовувати кількість шляхів для кожної з вершин на шляху з . Оскільки обчислення кожної з вершин будуть вестися рівно один раз, то трудомісткість алгоритму становитиме .
2.4. Черга з пріоритетами
Розглянемо безліч об'єктів і . Вважатимемо, що у безлічі об'єктів задано ставлення часткового порядку «менше чи одно», а еле-
менти множини занумеровані числами від 1 до
. Черга з пріоритетом
для безлічі елементів з і заданої функції
бій АТД з наступними операціями:
видалення елемента з мінімальним ключем.
Елементи множини будемо називатипріоритетами. Відповідно, операція видалення елемента з мінімальним ключем – це пошук та видалення
елемента, пріоритет якого є найменшим серед усіх елементів, що перебувають у черзі на даний момент.
Назва "Черга з пріоритетами" обумовлена видом упорядкування, якому піддаються дані, що зберігаються за допомогою АТД. Термін "черга" передбачає, що елементи очікують деякого обслуговування, а термін "пріоритет" визначає послідовність обробки елементів. Необхідно відзначити, що на відміну від звичайних черг, розглянутих у розд. 2.2, АТД «Черга з пріоритетами» не дотримується принципу FIFO.
Реалізація АТД «Черга з пріоритетами» може базуватись на основі масивів чи спискових структур. Серед останніх обирають як зв'язкові списки, і лінійні АТД. Незалежно від типу використовуваної лінійної структури даних, всі реалізації черги з пріоритетами можна умовно розділити на два типи щодо того, зберігаються елементи черги в упорядкованому вигляді чи ні. У разі впорядкованих послідовностей операцію пошуку та видалення елемента з мінімальним пріоритетом можна виконати.