Аналіз складності алгоритмів

Поняття алгоритму

Поняття алгоритму є одним з основних понять сучасної математики. Ще на ранніх щаблях розвитку математики (Стародавній Єгипет, Вавилон, Греція) в ній стали виникати різні обчислювальні процеси чисто механічного характеру. З їх допомогою шукані величини ряду завдань обчислювалися послідовно з вихідних величин за певними правилами та інструкціями. З часом всі такі процеси в математиці отримали назву алгоритмів (алгорифм).

Термін алгоритм походить від імені великого середньовічного узбецького математика Аль-Хорезмі, який ще в IX ст. (825) дав правила виконання чотирьох арифметичних дій у десятковій системі числення. Процес виконання арифметичних дій був названий алгорізмом.

З 1747 р. замість слова алгорізм стали вживати алгорісмус, сенс якого полягав у комбінуванні чотирьох операцій арифметичного обчислення ‒ додавання, віднімання, множення, ділення. З 1950 алгорісмус став алгорифмом. Сенс алгорифма найчастіше зв'язувався з алгорифмом Евкліда ‒ процесами знаходження найбільшого загального дільника двох натуральних чисел, найбільшою загальної міри двох відрізків, тощо.

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

Без алгоритмів неможливо створити жодну комп'ютерну програму. Тому в міру того, як комп'ютерні програми стають все більш значущими практично у всіх сферах професійної діяльності, вивчення алгоритмів стає все більш і більш важливим завданням для широкого кола людей. Процес вивчення алгоритмів полягає в розвитку вміння аналітично мислити. Зрештою, алгоритми можна розглядати як особливий підхід до вирішення завдань, коли важливі не стільки самі відповіді, скільки точні інструкції для їх отримання. Отже, спеціальні методи проектування алгоритмів можна вважати стратегічним планом вирішення завдання, яке стане в нагоді в будь-якому випадку, незалежно від того, використовується комп'ютер чи ні. Само собою зрозуміло, що коло завдань, які можуть бути вирішені за допомогою алгоритму по суті залежить від точності алгоритмічного мислення.

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

Це визначення можна проілюструвати за допомогою простої схеми (рис. 1.1).

Рис. 1.1. Ілюстрація поняття алгоритму

Кожен крок алгоритму має бути чітко і однозначно визначений. Ця вимога є обов'язковою і не повинна порушуватися ні за яких обставин.

Повинні бути точно вказані діапазони допустимих значень вхідних даних, які обробляються за допомогою алгоритму.

Один і той же алгоритм можна представити кількома різними способами.

Для вирішення однієї і тієї ж задачі може існувати кілька різних алгоритмів.

В основу алгоритмів для вирішення однієї і тієї ж задачі можуть бути покладені абсолютно різні принципи, що може істотно вплинути на швидкість вирішення цього завдання.

Алгоритми, відповідно до яких рішення поставлених завдань зводиться до арифметичних дій, називаються чисельними алгоритмами.

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

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

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

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

• механічні, або детерміновані (жорсткі);

• гнучкі, або стохастичні (імовірнісні та евристичні).

Механічний алгоритм задає певні дії, позначаючи їх в єдиній послідовності, що забезпечує однозначний необхідний (шуканий) результат в тому випадку, якщо виконуються умови процесу, для яких розроблений алгоритм. До таких алгоритмів відносяться алгоритми роботи машин, верстатів, двигунів тощо.

Імовірнісний (стохастичний) алгоритм пропонує програму рішення задачі кількома шляхами або способами, що призводять до досягнення результату.

Евристичний алгоритм (від грецького слова «еврика») ‒ це такий алгоритм, у якому досягнення кінцевого результату однозначно не визначено, так само як не позначена вся послідовність дій. У цих алгоритмах використовуються універсальні логічні процедури і способи прийняття рішень, засновані на аналогіях, асоціаціях і минулому досвіді вирішення схожих завдань. При реалізації евристичних алгоритмів велику роль відіграє інтуїція розробника.

У програмуванні алгоритми поділяються на три типи:

• лінійний ‒ набір команд (вказівок), які виконуються послідовно один за одним (рис. 1.2);

Рис. 1.2. Приклад лінійного алгоритму

• розгалужений ‒ алгоритм, який містить хоча б одну перевірку умови, в результаті якої забезпечується перехід на один з можливих варіантів рішення (рис. 1.3);

Рис. 1.3. Приклад розгалуженого алгоритму

• циклічний ‒ алгоритм, що передбачає багаторазове повторення одної і тої ж дії (одних і тих же операцій) над новими вихідними даними (рис. 1.4). До циклічних алгоритмів зводиться більшість методів обчислень і перебору варіантів.

Рис. 1.4. Приклад циклічного алгоритму

Допоміжний (підлеглий) алгоритм ‒ алгоритм, який розроблений заздалегідь і повністю використовується при алгоритмізації конкретного завдання.

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

Процес побудови алгоритму методом послідовної деталізації полягає в наступному. Спочатку алгоритм формулюється в «великих» блоках (командах), які можуть бути незрозумілі виконавцю (не входять в його систему команд) і записуються як виклики допоміжних алгоритмів. Потім відбувається деталізація, і всі допоміжні алгоритми докладно розписуються з використанням команд, зрозумілих виконавцеві.

Властивості алгоритмів

Під час розв’язання будь-якої задачі звичайно виходять з наявності з деяких початкових даних і мають уявлення про результат, який треба одержати. Приступаючи до рішення, спочатку намічають план і послідовність дій, які від початкових даних повинні привести до шуканого результату, тобто прагнуть побудувати алгоритм розв’язання. Такий ланцюжок дій, кожна з яких, за припущенням, відомим способом здійснена, і складає алгоритм; його виконання називається алгоритмічним процесом, а кожна ланка цього ланцюжка ‒ кроком алгоритмічного процесу, або алгоритму. Можна сказати, що алгоритм вказує послідовність дій з переробки початкових даних у результат.

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

Почергове виконання команд алгоритму за кінцеве число кроків приводить до вирішення завдання, до досягнення мети. Поділ виконання рішення задачі на окремі операції (виконувані виконавцем за певними командам) ‒ важлива властивість алгоритмів, звана дискретністю.

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

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

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

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

Будь-який алгоритм складається у розрахунку на конкретного виконавця з урахуванням його можливостей. Для того щоб алгоритм міг бути виконаний, не можна включати в нього команди, які виконавець не в змозі виконати. У кожного виконавця є свій перелік команд, які він може виконати. Сукупність команд, які можуть бути виконані виконавцем, називається системою команд виконавця. Кожна команда алгоритму повинна визначати однозначно дію виконавця. Така властивість алгоритмів називається визначеністю (або точністю) алгоритму.

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

Таким чином, зрозумілість ‒ знання виконавця про те, що треба робити для виконання цього алгоритму. При цьому виконавець алгоритму, виконуючи його, діє «механічно», тому формулювання алгоритму має бути настільки точне й однозначне, щоб могло повністю визначати всі дії виконавця. Людина, навіть не втаємничена в тій сфері, для розв’язання задач якої розроблений алгоритм, але яка розуміє вказівки, що містяться в ньому і точно їх виконує, ‒ обов’язково дістає шукане розв’язання задачі.

Ще одна важлива вимога, що пред'являється до алгоритмів, ‒ результативність алгоритму. Вона означає, що виконання алгоритму має закінчитися за кінцеве число кроків. Тобто смисл результативності полягає в тому, що алгоритмічний процес повинен бути кінцевим: за певне число кроків повинен бути добутий шуканий результат або доведено, що алгоритм не застосований до даної множини початкових даних. Непридатність алгоритму до допустимих початкових даних має місце або під час порушення умови скінченності алгоритмічного процесу, необхідною виявляється нескінчена кількість кроків алгоритму, або під час виникнення непереборних перешкод до його виконання на якомусь кроці.

У математиці є обчислювальні процеси, що мають алгоритмічний характер, але не володіють властивістю кінцівки. Так можна сформулювати процедуру обчислення числа . Така процедура описує нескінченний процес і ніколи не завершиться. Якщо спосіб отримання наступної величини з якоїсь заданої не приводить до результату, то повинна бути вказівка, що треба вважати результатом алгоритму. У нашому випадку можна ввести умову завершення процесу обчислення виду: «Закінчити обчислення після отримання n десяткових знаків числа », ‒ то вийде алгоритм обчислення n десяткових знаків числа . На цьому принципі базується отримання багатьох обчислювальних алгоритмів: будується нескінченний, збіжний до шуканого розв’язку процес. Він обривається на певному кроці, і добуте значення приймається за наближений розв’язок задачі, що розглядається. При цьому точність наближення залежить від числа кроків.

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

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

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

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

Ефективність алгоритму. Під ефективністю алгоритму будемо розуміти таку його властивість (якість), яка дозволяє вирішити завдання за прийнятний для розробника час. До параметру, що характеризує ефективність алгоритму, слід віднести також обсяг пам'яті комп'ютера, необхідний для вирішення завдання.

Формальність ‒ результат виконання алгоритму не повинен залежати від будь-яких факторів, які не є частиною цього алгоритму. Будь-який виконавець, здатний сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи за алгоритмом, може виконати поставлене завдання. Ця властивість має особливе значення для виконання алгоритмів. Очевидно, електронно-обчислювальні машини не можуть розуміти суті завдань і окремих вказівок алгоритмів, хоча успішно виконують різні алгоритми.

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

Аналіз складності алгоритмів

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

1) бути простим для розуміння, перекладу в програмний код і налагодження;

2) ефективно використовувати обчислювальні ресурси і виконуватися по можливості швидко.

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

Складність алгоритму ‒ це величина, що відображає порядок величини необхідного ресурсу (часу або додаткової пам'яті) залежно від розмірності задачі.

Таким чином, будемо розрізняти тимчасову Т(n) і просторову V(n) складності алгоритму. При розгляді оцінок складності будемо використовувати тільки тимчасову складність. Просторова складність оцінюється аналогічно.

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

1) тимчасова складність алгоритму програми;

2) якість скомпільованого коду виконуваної програми;

3) машинні інструкції, використовувані для виконання програми.

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

Існує метод, що дозволяє теоретично оцінити час виконання алгоритму.

Часто, тимчасова складність алгоритму залежить від кількості вхідних даних. Зазвичай кажуть, що тимчасова складність алгоритму має порядок Т(n) від вхідних даних розміру n. Точно визначити величину Т(n) на практиці виявляється досить важко. Тому вдаються до асимптотичних відносин з використанням О-символіки.

Наприклад, якщо число тактів (дій), необхідних для роботи алгоритму, виражається як , то це алгоритм, для якого Т(n) має порядок . Фактично, з усіх доданків залишається тільки той, який вносить найбільший вклад при великих n (в цьому випадку рештою з доданків можна знехтувати) і ігнорується коефіцієнт перед ним.

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

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

Таблиця 1

n
1	0	0	1
16	4	64	256
256	8	2 048	65 536
4 096	12	49 152	16 777 216
65 536	16	1 048 565	4 294 967 296
1 048 476	20	20 969 520	1 099 301 922 576
16 775 616	24	402 614 784	281 421 292 179 456

Якщо вважати, що числа відповідають мікросекундам, то для завдання з 1 048 476 елементами алгоритму з часом роботи  буде потрібно 20 мікросекунд, а алгоритму з часом роботи  ‒ більше 12 днів.

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

Слід звернути увагу, що основа логарифму тут не пишеться. Причина цього досить проста. Нехай є . Але , a , як і будь-яку константу, символ  не враховує. Таким чином, . До будь-якої основи можна перейти аналогічно, а значить, і писати її не має сенсу.

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

· максимальну складність , або складність найбільш несприятливого випадку, коли алгоритм працює найдовше;

· середню складність  ‒ складність алгоритму в середньому;

· мінімальну складність  ‒ складність в найбільш сприятливому випадку, коли алгоритм справляється найшвидше.

Теоретична оцінка часової складності алгоритму здійснюється з використанням наступних базових принципів:

1) час виконання операцій привласнення, читання, записи зазвичай мають порядок . Винятком є оператори присвоювання, в яких операнди являють собою масиви або виклики функцій;

2) час виконання послідовності операцій збігається з найбільшим часом виконання операції в даній послідовності (правило сум: якщо  має порядок , а  ‒ порядок , то  має порядок ;

3) час виконання конструкції розгалуження (if-then-else) складається з часу обчислення логічного виразу (зазвичай має порядок  і найбільшого з часу, необхідного для виконання операцій, виконуваних при істинному значенні логічного виразу і при помилковому значенні логічного виразу;

4) час виконання циклу складається з часу обчислення умови припинення циклу (зазвичай має порядок ) і виразу кількості виконаних ітерацій циклу на найбільш можливий час виконання операцій тіла циклу.

5) час виконання операції виклику процедур визначається як час виконання викликаємої процедури;

6) за наявності в алгоритмі операції безумовного переходу, необхідно враховувати зміни послідовності операцій, які здійснюються з використанням цих операції безумовного переходу.