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

begin

bpp := (cpp - 1)*2*lp + 1;

{ індекс першого елемента лівої ділянки пари}

mrg ( B, bpp, lp, lp, A );

end;

{ обробка залишку }

if tl > lp then

mrg ( B, n - tl + 1, lp, tl - lp, A );

{ за tl <= lp залишок був упорядкований }

{ на попередньому кроці }

lp := lp*2

end

{ lp >= n : масив упорядковано на останньому кроці }

end

Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1
lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp,

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

Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ log2n =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).

Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+ log2n ) та округлене відношення r двох останніх:

nn(n-1)/2n(1+ log2n )r

1045401

10049507007

10004995001000050

1000049995000140000350