Page 23 - 4761

Алгоритм логарифмічного пошуку заключається в наступному: шуканий елемент
порівнюється з елементом (N +1)/2 в середині таблиці. Якщо цей елемент не є шуканим,
то ми переглядаємо тільки блок елементів від 1 до (N +1)/(2-1), або блок (N +1)/2 + 1 до N
залежно від того «<» чи «>» шуканий елемент від того, з яким його порівнюють. Потім
процес повторюється над потрібним блоком в 2 рази меншого розміру. Так продовжується
до тих пір, поки шуканий елемент не буде знайдено.
Так як на кожному кроці число елементів, які можуть містити шуканий елемент,
скорочується в 2 рази, то максимальне число порівнянь рівне 1+log 2(N). Тоді як час
пошуку елемента в таблиці ідентифікаторів можна оцінити як Т П = О(log 2(N)). Для
порівняння: при N = 128 логарифмічний (бінарний) пошук максимально потребує 8
порівнянь, а звичайний пошук в таблиці – 64. Метод називається бінарним пошуком,
оскільки число інформації, яку розглядаємо, скорочується в 2 рази. А метод –
логарифмічний, оскільки час, який затрачаємо на пошук потрібного елемента в масиві,
має логарифмічну залежність від кількості елементів у ньому.
Недолік: потреба впорядковувати ТІ, і час її заповнення залежить від кількості
елементів. ТІ часто переглядають ще до того, як вона заповнена повністю, тому її треба
впорядковувати на кожному етапі звернення до неї. Тому, при побудові такої таблиці
використовують алгоритм прямого впорядкованого включення елемента.
При додаванні елемента в таблицю спершу треба визначити, куди його помістити, а
потім виконати перенос частини інформації, якщо елемент додається не в кінець таблиці.
Середній час, необхідний для розміщення всіх елементів до ТІ:
2
Т З = О(N * lg 2(N)) + К*О(N )
К – деякий коефіцієнт, який відображає співвідношення між часом, який витрачає
комп’ютер на виконання операції порівняння й операції переносу даних.
Таким чином, при організації логарифмічного пошуку в ТІ суттєвого скорочення
часу на пошук шуканого елемента можна добитись за рахунок збільшення часу на
розміщення нового елемента в таблиці. Оскільки розміщення відбувається рідше, то цей
алгоритм є більш ефективним.

Побудова ТІ за методом бінарного дерева
Можна скоротити час пошуку шуканого елемента в ТІ, не збільшуючи значно час,
необхідний для її заповнення. Для цього треба відмовитись від організації таблиць у
вигляді неперервного масиву даних.
Існує метод побудови ТІ, при якому ТІ має форму бінарного дерева. Кожен вузол
дерева – елемент таблиці, причому кореневий вузол є першим елементом при заповненні
таблиці. Дерево називається бінарним, так як кожна вершина в ньому може мати не
більше двох гілок: ліву і праву.
Розглянемо алгоритм побудови ТІ за методом бінарного дерева.
Перший ідентифікатор поміщаємо у вершину дерева, а далі :
К1: Вибрати черговий ідентифікатор із вхідного потоку даних. Якщо чергового
ідентифікатора нема, то дерево побудовано.
К2: Зробити поточним вузлом дерева кореневу вершину.
К3: Порівняти черговий ідентифікатор з ідентифікатором в поточному вузлі дерева.
К4: Якщо черговий ідентифікатор менший, то перейти на К5; якщо дорівнює –
повідомити про помилку і припинити виконання алгоритму (2-х однакових
ідентифікаторів немає), інакше – на К7.
К5: Якщо у поточного вузла є ліва вершина, то зробити її поточною і повернутись
до К3, інакше – до К6.
К6: Створити нову вершину, помістити в неї черговий ідентифікатор, зробити її
лівою вершиною поточного вузла, далі до К1.

21