Основы объектно-ориентированного программирования на языке C# book | Page 39

2.3 Складнiсть задач
Oцiнимо алгоритм бiнарного пошуку ключа в упорядкованому ма-
сивi. Суть алгоритму: розглядаємо серединний елемент масиву й пе-
ревiряємо вiдповiднiсть ключа до його значення. Якщо не вдається
знайти вiдповiднiсть, то порiвнюємо ключ i значення серединного еле-
мента, а потiм перемiщаємося в нижню половину списку елементiв
масиву, якщо ключ менше, i верхню – якщо бiльше. В обранiй поло-
винi знову шукаємо середину та знову порiвнюємо iз ключем. Якщо
не виходить, то знову дiлимо надвоє поточний iнтервал.
Розглянемо детальнiше алгоритм. Вхiд: low, high – змiннi, що за-
дають нижню й верхню межi масиву, key – шукане число.
1. поки low ≤ high виконувати
2. початок
3. mid = (low + high)/2;
4. data = a[mid];
5. якщо key = data
6. тодi початок search = mid; закiнчити роботу кiнець
7. iнакше якщо key < data
8. то high = mid − 1
9. iнакше low = mid + 1;
10. кiнець;
11. search = −1;
Перша iтерацiя циклу має справу з усiм списком елементiв. Ко-
жна подальша iтерацiя дiлить список навпiл. Наприклад, розмiрами
спискiв для послiдовних крокiв алгоритму є n, n/2, n/2 2 , ... n/2 m .
Урештi–решт знайдеться таке цiле m, що n/2 m < 2 або n < 2 m+1 .
Oскiльки m – перше цiле, для якого n/2 m < 2, то має бути вiрним
n/2 m − 1 ≥ 2 або 2 m ≤ n. Iз цього випливає, що 2 ≤ n < 2 m + 1.
Вiзьмемо логарифм кожноı̈ частини нерiвностi й дiстанемо m ≤
log 2 (n) = x < m + 1. Значення m – найбiльше цiле, що менше або
дорiвнює x. Oтже, складнiсть дорiвнює O(n log 2 n).
Знайдемо вираз для часу, що необхiдний програмi для обробки ма-
сиву з N елементами як функцiю вiд N . Зазвичай нас цiкавить сере-
днiй випадок – очiкуваний час роботи програми на типових вхiдних
даних, i гiрший – очiкуваний час роботи програми на найгiрших вхi-
дних даних.
Через труднощi, пов’язанi з проведенням аналiзу часовоı̈ складностi
алгоритму в середньому, часто доводиться задовольнятися оцiнками
39