1 of 29

Поняття складності алгоритмів

За навчальною програмою 2017 року

Урок 57

Інформатика 9

teach-inf.com.ua

за підручником

Ривкінд Й.Я. та ін.

2 of 29

Поняття складності алгоритму

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

дані з вимірювальних пристроїв, що неперервно надходять, наприклад, з датчиків, що визначають стан ядерного реактора;

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

дані з метеорологічних станцій, що розташовані в багатьох точках Земної кулі;

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

Розділ 5

§ 5.3

3 of 29

Поняття складності алгоритму

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

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

Розділ 5

§ 5.3

4 of 29

Поняття складності алгоритму

Швидкість роботи алгоритму визначається його складністю.

Складність алгоритму – це комплексна властивість алгоритму, яка визначає:

Часова складність алгоритму – час, необхідний для виконання алгоритму, який залежіть від кількості операцій, які потрібно виконати в алгоритмі;

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

ємнісну складність алгоритму

Розділ 5

§ 5.3

5 of 29

Поняття складності алгоритму

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

Розділ 5

§ 5.3

6 of 29

Поняття складності алгоритму

Часова та ємнісна складність алгоритму тісно пов’язані між собою і кожна з них залежить від обсягу вхідних даних.

Якщо б кожна операція в комп’ютері виконувалася протягом одного й того самого часу t₀, то часову складність алгоритму Т можна було б обчислити за формулою:

Т = t₀*n

кількість операцій

n

Розділ 5

§ 5.3

7 of 29

Поняття складності алгоритму

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

Розділ 5

§ 5.3

8 of 29

Поняття складності алгоритму

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

Складність такого алгоритму називається константною і позначається О(1).

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

Розділ 5

§ 5.3

9 of 29

Поняття складності алгоритму

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

Складність такого алгоритму називається лінійною і позначається О(n).

Розділ 5

§ 5.3

10 of 29

Поняття складності алгоритму

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

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

Розділ 5

§ 5.3

11 of 29

Поняття складності алгоритму

Якщо алгоритм містить вкладені один в інший два цикли, то час виконання такого алгоритму пропорційний деякій константі, помноженій на квадрат кількості вхідних даних n².

Складність такого алгоритму називається квадратичною і позначається О(n²).

Розділ 5

§ 5.3

12 of 29

Поняття складності алгоритму

Це означає, що якщо кількість вхідних даних збільшити, наприклад, у 5 разів, то час виконання алгоритму збільшиться в 5²=25 разів.

Такими алгоритмами є, наприклад, розглянуті в цьому пункті алгоритми впорядкування одновимірного масиву з n елементів. У таких алгоритмах вхідні дані переглядаються приблизно n² разів.

Розділ 5

§ 5.3

13 of 29

Поняття складності алгоритму

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

Це означає, що якщо кількість вхідних даних збільшити, наприклад, у 5 разів, то час виконання алгоритму збільшиться в 5³=125 разів. У таких алгоритмах вхідні дані переглядаються приблизно n³ разів.

Розділ 5

§ 5.3

14 of 29

Поняття складності алгоритму

Лінійна, квадратична, кубічна складності є частковими випадками поліноміальної складності, яка позначається О(n^m), де m – натуральне число.

Розрізняють ще й інші види складності алгоритмів. З поняттям складності алгоритму безпосередньо пов’язано поняття його ефективності.

Алгоритм, який виконується швидше і/або використовує менший об’єм пам’яті, вважається ефективнішим. Тому чим менша складність алгоритму, тим він ефективніший.

Розділ 5

§ 5.3

15 of 29

Поняття складності алгоритму

Ефективність алгоритму може залежати від набору вхідних даних. Так якщо порівняти розглянуті в цьому пункті алгоритми впорядкування одновимірних масивів з n елементів, то з’ясується, що для невеликої кількості елементів (n < 100) швидше виконується алгоритм впорядкування методом обміну, а для (n ≥ 100) – алгоритм впорядкування методом вибору.

Для розв’язування однієї й тієї ж задачі можна скласти алгоритм різної складності, а значить й різної ефективності. Розглянемо одну таку задачу.

Розділ 5

§ 5.3

16 of 29

Поняття складності алгоритму

У попередньому пункті був розглянутий алгоритм розв’язування аналогічної задачі, в якому елементи масиву послідовно порівнюються із даним числом. В найгіршому випадку таких порівнянь буде виконано n. Це буде у випадку, коли числа в масиві немає або якщо воно буде останнім елементом масиву.

Задача. Дано впорядкований за зростанням одновимірний масив з n елементів і ще одне число. Визначити, чи є це число серед елементів масиву.

Розділ 5

§ 5.3

17 of 29

Поняття складності алгоритму

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

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

Розділ 5

§ 5.3

18 of 29

Поняття складності алгоритму

Далі порівняємо дане число із значенням елемента, який розташований посередині визначеної половини масиву.

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

Розділ 5

§ 5.3

19 of 29

Поняття складності алгоритму

Цей алгоритм називається алгоритмом половинного поділу. Він був відомий ще стародавнім грекам і називався дихотомією.

Якщо порівняти ефективності алгоритму послідовного перегляду і алгоритм половинного поділу, то при

n = 1000,

в першому алгоритмі потрібно виконати

а в другому алгоритмі потрібно виконати

максимум 1000 порівнянь

максимум 10 порівнянь

Розділ 5

§ 5.3

20 of 29

Для тих, хто хоче знати більше

Використання великої літери О для позначення складності алгоритму (так звана О-нотація) була запозичена з математики. Там її застосовують для позначення, до значень якої функції асимптотично (все ближче і ближче) наближаються значення даної функції.

Наприклад, для малих додатних значень х значення функції у = х² дуже мало відрізняється від значень функції у = х, і тому х² = О(х). А для великих додатних значень х значення функції у = х² + х³ дуже мало відрізняється від значень функції у = х³, і тому х³ + х² = О(х³).

Розділ 5

§ 5.3

21 of 29

Цікаві факти з історії

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

З появою комп’ютерів на початку 40-х років ХХ ст. обсяг даних для опрацювання постійно збільшувався. І для зменшення часу роботи програм опрацювання цих даних розробляли більш ефективні алгоритми впорядкування.

Розділ 5

§ 5.3

22 of 29

Цікаві факти з історії

Такі алгоритми розробили відомі математики і програмісти:

Чарльз Хоар

(нар. 1934, Велика Британія)

Дональд Шелл (1924 – 2015, США)

Дональд Кнут (нар. 1938, Велика Британія)

Едсгер Дейкстра (1930–2002, Нідерланди)

Джон фон Нейман

(1903–1957, Угорщина, США)

Розділ 5

§ 5.3

23 of 29

Цікаві факти з історії

Українські науковці багато років займаються вдосконаленням та застосуванням алгоритмів впорядкування для оптимізації обчислень. Проблемами впорядкування даних займалися дослідники Інституту кібернетики імені В. М. Глушкова НАН України для організації обчислень на комп’ютерах із розподіленою пам’яттю.

Розділ 5

§ 5.3

24 of 29

Цікаві факти з історії

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

Суттєвий внесок в дослідженні цих питань внесли українські вчені Жалдак М.І. і Тріус Ю.В.

Жалдак М.І.

Розділ 5

§ 5.3

25 of 29

Дайте відповіді на запитання

Що таке складність алгоритму?

Що означають складності алгоритмів О(1), О(n), О(n2), О(n3)?

Розділ 5

§ 5.3

26 of 29

Розгадайте ребус

Складність

Розділ 5

§ 5.3

27 of 29

Домашнє завдання

Проаналізувати

§ 5.3, с. 265-270

Розділ 5

§ 5.3

28 of 29

Працюємо за комп’ютером

Сторінка

270

Розділ 5

§ 5.3

29 of 29

Дякую за увагу!

За навчальною програмою 2017 року

Урок 57

Інформатика 9

teach-inf.com.ua

за підручником

Ривкінд Й.Я. та ін.