Функція F(n) називається функцією порядку, меншого від G(n) за великих n, і це позначається F(n)=o(G(n)), якщо .

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

Приклад 1. n? (n-1) = O(n2), оскільки за n > 2 маємо

0.5? n2 < n*(n-1) < n2.

Аналогічно неважко довести, що n3 + 100? n2 = O(n3) = o(n3.1) = o(2n), 100? logn + 10000 = O(logn) = O(lgn) = o(n).

Приклад 2. Складність алгоритму бульбашкового сортування tb(n)=O(n2), алгоритму лінійного пошуку – t1(n)=O(n), бінарного пошуку – t2(n)=O(logn)=o(n).

Тепер означимо поняття складності задачі. Алгоритми пошуку в упорядкованому масиві свідчать, що одна й та сама задача може мати алгоритми розв'язання з різною складністю. Неформально, під складністю задачі розуміють найменшу зі складностей алгоритмів її розв'язання. Іншими словами, задача має складність порядку G(n), якщо існує алгоритм її розв'язання зі складністю O(G(n)) і не існує алгоритмів зі складністю o(G(n)).

Наприклад, складність задачі пошуку в упорядкованому масиві визначається складністю алгоритму двійкового пошуку, тому й оцінюється функцією logn. Задача сортування масиву має складність порядку n? logn. Доводити ці факти ми не будемо – можна подивитися, наприклад, у книгу [АХУ]. Але в наступному параграфі ми наведемо алгоритми сортування з цією оцінкою складності.

Задачі

5. Оцінити складність задачі

а) * про Ханойські вежі (підр.9.3); б) пошуку підмножини (підр.9.2).

6.* Оцінити складність алгоритмів сортування вибором та простими вставками (задачі 17.3, 17.4).

7.* Задача про неспадну підпослідовність. Задано n-елементний масив цілих, n<10000. Знайти:

а) максимальну довжину неспадних підпослідовностей значень масиву;

б) неспадну підпослідовність значень масиву максимальної довжини. Якщо таких кілька, то з них вибиpається та, що має найменшу суму елементів. Напpиклад, за масиву зі значеннями <2, 1, 5, 3> це буде <1, 3>.

Складність алгоритму повинна бути якомога меншою.

4. Ефективні алгоритми сортування

4.1. Сортування злиттям

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.

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

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,

Y | … | 1 | 3 | … | 13 | 2 | 4 | … | 88 

… | m | m+1  | m+s-1 | m+s | m+s+1 | … | m+s+r

Результатом злиття повинна бути ділянка довжини r+s у масиві X:

X | … | 1 | 2 | 3 | 4 | … | 13 | … | 88 

… | m | m+1 | m+2 | m+3  | …  | m+s+r

За дії означень (17.1) таке злиття двох ділянок у масиві Y у ділянку масиву X задає процедура

procedure mrg( var Y : ArT; m, s, r : Indx; var X : ArT);

var mr, k : Indx; i, j : Extind;

begin

mr := m + s; { mr – початок правої частини }

i := m; j := mr; { i та j пробігають ліву й праву ділянки масиву Y}

for k := m to m + s + r - 1 do{заповнення X[m], … , X[m+s+r-1]}

if i > m + s - 1 then

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

if j > mr + r - 1 then

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

if Y[i] < Y[j] then

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

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

end

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], … , A[n] копіюються в допоміжний масив B[1], … , B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.

На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.

Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.

Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";":

< <11><10> ; <9><8> ; <7><6> ; <5><4> ; <3><2> ; <1> >, lp=1

< <10, 11><8, 9> ; <6, 7><4, 5> ; <2, 3><1> >, lp=2

< <8, 9, 10,