Пошук сортування та поняття складності у програмуванні

ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

1. Пошук за ключем у масиві

1.1. Лінійний пошук

Читачеві колись доводилося шукати своє прізвище в списках, надрукованих не в алфавітному порядку? Або уявіть собі словник на 100 тисяч слів, розташованих там без упорядкування за алфавітом. Потрібне слово шукати там доведеться довго. Дуже довго. Звичайно, якщо воно випадково не потрапило в самісінький початок. А якщо в кінець чи середину? А пошук слова в "нормальному" словнику займає чомусь кілька секунд незалежно від його розташування там.

У цьому параграфі ми наведемо два алгоритми. Перший описує пошук "підряд" у невпорядкованій послідовності, другий – той пошук, до якого ми звикли, шукаючи слова в словниках. Замість слів розглянемо цілі значення елементів масиву. Тип значень може бути й іншим – головне, щоб їх можна було порівнювати.

Нехай елементи масиву A [1], A [2], … , A [n ] та змінна key ("ключ") мають той самий тип T. Пошук за ключем полягає в пошуку номера i такого, що A [i ]= key . За відсутності такого номера результатом будемо вважати 0. Нехай діють означення

const maxn = 1000;

type T = integer;

Indx = 1 .. maxn; (17.1)

ArT = array [Indx] of T;

Подамо розв'язання задачі функцією

function srcseq ( var A : ArT; n : Indx; key : T) : integer;

var i : integer;

begin

i := 0;

while ( i <= n ) do

if A[i]<> key then i := i + 1 else break ;

{ i = n + 1 або A[i] = key }

if i < n + 1 then srcseq := i

else srcseq := 0

end

З'ясуємо, яким чином час пошуку за цим алгоритмом залежить від кількості n елементів масиву. Узагальнимо присвоювання та операції над значеннями скалярних типів (порівняння, додавання, множення тощо) терміном елементарна дія . Будемо вважати, що на виконання кожної елементарної дії витрачається скінченний обмежений проміжок часу, незалежний від конкретних операндів . За такого припущення час виконання програми (підпрограми) прямо пропорційний кількості елементарних дій у процесі виконання.

Очевидно, що кількість елементарних дій при виконанні функції srcseq прямо пропорційна кількості порівнянь A[i]<>key. В найгіршому випадку з ключем порівнюються всі елементи масиву. Звідси максимальна кількість дій та найбільший час виконання функції прямо (лінійно) пропорційні n , і найбільший час пошуку t ₁ є лінійною функцією від кількості елементів масиву. Описаний спосіб пошуку називається лінійним . Лінійну залежність часу від кількості елементів, тобто довжини n , будемо позначати символом "O": t ₁ = O(n ).

1.2. Дихотомічний пошук

Тепер опишемо так званий дихотомічний пошук у "нормальному словнику". Ми розкриваємо словник приблизно в його середині. Якщо слово повинно бути в словнику далі, то шукати треба лише в другій половині словника. Його середина стає для нас початком, і ми розкриваємо його на середині другої половини. Аналогічно, коли слово повинно бути в першій половині, ми залишаємо для пошуків лише її. Отже, кожне заглядання в словник поділяє "простір пошуку" на дві половини й зменшує його приблизно вдвічі. Звідси й назва, оскільки дихотомія – це поділ на дві половини. Такий пошук ще називають двійковим , або бінарним .

Нехай значення елементів масиву упорядковані за зростанням, тобто A [1]£ A [2]£ … £ A [n ] (кажуть, масив відсортований ). Опишемо дихотомічний пошук такою функцією:

function srcbin ( var A : ArT; n : Indx; key : T) : integer;

var i, hb, lb : integer;

begin

lb := 1; hb := n;

i := (lb + hb) div 2;

while (lb < hb) do

begin

if A[i] = key then break else

if A[i] > key

then hb := i - 1 { key може бути лише ліворуч від A[i] }

else lb := i + 1; { key може бути лише праворуч від A[i] }

i := (lb + hb) div 2

end ;

{ lb >= hb або A[i] = key }

if (i=0) or (i=n+1) then srcbin := 0 else

if A[i] = key then srcbin := i else srcbin := 0

end

Виконання тіла циклу while вимагає сталого числа елементарних дій незалежно від значень змінних A, key, i, lb, hb. Звідси загальна кількість дій прямо пропорційна кількості повторень тіла циклу while . Але за кожного повторення різниця hb-lb зменшується принаймні у два рази. Спочатку hb-lb = n - 1, тому виконань тіла циклу не більше ніж log₂ n , звідки час виконання функції t ₂ = O(log₂ n ).

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать