Сторінка
3
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<¥ . Функція 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 |
|
X |
… |
1 |
2 |
3 |
4 |
… |
13 |
… |
88 |
|
… |
m |
m+1 |
m+2 |
m+3 |
… |
m+s+r |
Завантажити реферат