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

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 Розглянемо найпростіший (і найгірший з точки зору витрат часу) спосіб сортування масиву. Нехай A[1], A[2], ... , A[n] – масив із довільними значеннями елементів. Порівняємо A[1] і A[2]: якщо A[1]>A[2], то поміняємо їхні значення місцями. Потім порівняємо A[2] і A[3] та за необхідності обміняємо їхні значення. В результаті A[3] має найбільше значення серед A[1], A[2], A[3]. Продовжимо такі порівняння та обміни до кінця масиву:

для всіх i від 1 до n-1 виконати

якщо A[i]>A[i+1], то

значення A[i] та A[i+1] обмінюються.

Якщо значення елементів розглядати як розміри бульбашок, то ці порівняння та обміни схожі на те, як більші бульбашки відтісняють менших униз і спливають нагору. Тому цей метод називається бульбашковим сортуванням. У результаті найбільша бульбашка стає верхньою, тобто останній елемент A[n] має найбільше значення. Наприклад, послідовність значень перетвориться на .

Далі почнемо все спочатку і перемістимо друге за величиною значення до передостаннього елемента A[n-1], перетворивши, наприклад, на . Потім третє за величиною значення перемістимо до A[n-2] тощо. Останній крок складається лише з порівняння A[1] A[i+1]

then swap (A[i], A[i+1])

end

Тут і далі процедура swap задає обмін значень своїх параметрів. Як бачимо, разом виконується (n-1)+(n-2)+…+1= n (n-1)/2 порівнянь. Очевидно, що найбільше можливе число елементарних дій за цим способом прямо пропорційне кількості порівнянь. Тому час сортування масиву з n елементів у такий спосіб прямо пропорційний n (n-1).

3. Поняття складності алгоритму та задачі

У цьому параграфі ми познайомимося з двома поняттями, які відіграють у програмуванні одну з ключових ролей. Цими поняттями є складність алгоритму та складність задачі. Почнемо з алгоритмів.

Нагадаємо, що алгоритм розв'язання масової задачі описує розв'язання будь-якого її екземпляра. Екземпляри багатьох задач можна охарактеризувати значенням деякого числового параметра. Наприклад, довжиною масиву чи кількістю чисел, які треба прочитати з клавіатури. Або натуральним числом, про яке ми хочемо дізнатися, чи просте воно. Найчастіше цим параметром є кількість скалярних значень, обробка яких задається алгоритмом. Кажуть, що екземпляр задачі має розмір N, якщо задається даними, складеними з N скалярних значень (наприклад, масивом із N елементів).

Нехай A позначає алгоритм розв'язання деякої масової задачі. Позначимо через F(A, екземпляр) кількість елементарних дій у процесі розв'язання цього екземпляра задачі за алгоритмом A, а через F(A, n) – максимум кількості елементарних дій серед усіх екземплярів розміру n.

Наприклад, якщо при бульбашковому сортуванні масив спочатку відсортований навпаки, то слідом за кожним порівнянням відбувається обмін. А це ще три присвоювання. Якщо нехтувати допоміжними операціями із змінами індексів, то

F(A, n)=4 n (n-1)/2.

Кожному n = 1, 2, 3, … відповідає певне значення F(A, n), тобто ми маємо функціональну залежність між розмірами n та максимальними кількостями елементарних дій, виконуваних за алгоритмом A. Ця функція називається складністю алгоритму A. Алгоритми практично всіх реальних задач мають складність, монотонно неспадну за n.

Аналітичне задання функції F(A, n) для реальних алгоритмів, як правило, неможливе й не потрібне. Велике практичне значення має так званий порядок зростання F(A,n) за n. Він задається за допомогою іншої функції з простим аналітичним виразом, яка є оцінкою для F(A, n).

Функція G(n) є оцінкою для функції F(n), або F(n) є функцією порядку G(n), коли існують такі додатні скінченні числа C1 і C2, що за деякого m при всіх n > m

C1 G(n)  F(n)  C2 G(n).

Така залежність між функціями позначається за допомогою знака "О":

F(n) = O(G(n)).

Для задання порядку зростання інколи користуються іншим означенням: функція F(n) називається функцією порядку G(n) за великих n, якщо , де C>0, C 2 маємо

0.5 n2 mr + r - 1 then

begin X[k] := Y[i]; i := i + 1 end else

if Y[i] lp,

і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.

Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2kОчевидно, що кожний елемент має значення, найбільше в тій піраміді, де він є вершиною. Наприклад, A[2] має значення, найбільше серед елементів із індексами 2, 4, 5, 8, 9, 10, 11. Зокрема, A[1] має значення, найбільше серед усіх елементів.

Якщо поміняти місцями значення A[1] і A[n], то елемент A[n] матиме найбільше значення. Про нього "можна забути" та зосередитися на сортуванні A[1], A[2], ... , A[n-1]. Зрозуміло, що умова A[1] A[2], A[1] A[3] після обміну може виявитися порушеною. Для її відновлення треба обміняти місцями значення A[1] та того з A[2], A[3], чиє значення максимальне. Нехай це буде A[3]. В останньому прикладі після обміну значень A[1] і A[12] на вершині піраміди значення 27, і 27 A[2*i+1] then k := 2*i

else k := 2*i + 1;

if A[i] A[hi]) then

begin

swap ( A[lo], A[hi] );

goto 1

end;

k := lo + 1; j := hi;

v := A[lo]; {?!}while ( k a[c[rr]].y)or

not( (tp.x>a[c[ll]].x)and(tp.x a[c[rr]].y)or

not( (tp.x>a[c[ll]].x)and(tp.x

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

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

Скачать