Пошук, сортування та поняття складності у програмуванні, Детальна інформація

Приклад 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\xF0D7 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