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

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 елементів масиву. Узагальнимо присвоювання та операції над значеннями скалярних типів (порівняння, додавання, множення тощо) терміном елементарна дія. Будемо вважати, що на виконання кожної елементарної дії витрачається скінченний обмежений проміжок часу, незалежний від конкретних операндів. За такого припущення час виконання програми (підпрограми) прямо пропорційний кількості елементарних дій у процесі виконання.