1 of 35

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

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

Урок 64

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

teach-inf.com.ua

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

Бондаренко О.О. та ін.

2 of 35

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

Який час потрібний для виконання програми, що реалізує певний алгоритм?

Чи вистачить ресурсів комп’ютера, щоб отримати результати обчислення за даним алгоритмом?

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

Розділ 5

§ 37

3 of 35

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

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

Розділ 5

§ 37

4 of 35

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

Складність алгоритмів зазвичай оцінюють за часом виконання або за використовуваною пам’яттю:

часова складність

ємнісна складність

час виконання алгоритму

кількість умовних одиниць пам’яті, необхідних для роботи алгоритму

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

Розділ 5

§ 37

5 of 35

Оцінка складності

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

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

Розділ 5

§ 37

6 of 35

Оцінка складності

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

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

Розділ 5

§ 37

7 of 35

Оцінка складності

Терміном елементарна операція позначимо присвоювання та операції над значеннями простих типів:

За такого припущення час виконання програми прямо пропорційний кількості елементарних операцій у процесі виконання.

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

порівняння

додавання

множення

Розділ 5

§ 37

8 of 35

Оцінка складності

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

Розділ 5

§ 37

9 of 35

Оцінка складності

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

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

Для позначення оцінки складності алгоритмів використовують так звану О-нотацію — вираз O(f(n)), який означає, що час виконання алгоритму зростає з тією ж швидкістю, що і функція f(n).

Розділ 5

§ 37

10 of 35

Оцінка складності

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

Якщо час роботи алгоритму не залежить від обсягу вхідних даних, то його часову складність позначають як O(1); наприклад, для визначення значення третього елемента масиву не потрібно ні запам’ятовувати елементи, ні проходити по них декілька разів, тобто на обчислення результату для будь-якої кількості даних потрібен той самий час.

Розділ 5

§ 37

11 of 35

Оцінка складності

Лінійну складність O(n) мають алгоритми, час виконання яких лінійно залежить від кількості вхідних даних,

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

Розділ 5

§ 37

12 of 35

Оцінка складності

Квадратична складність O(n²) визначається, якщо час роботи алгоритму зростає пропорційно квадрату кількості оброблюваних елементів,

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

Розділ 5

§ 37

13 of 35

Оцінка складності

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

тобто подвоєння розміру задачі збільшує необхідний час у вісім разів. Припустимо, певним алгоритмом потрібно виконати 2n³ + 5n умовних операцій, щоб обробити n елементів вхідних даних.

Розділ 5

§ 37

14 of 35

Оцінка складності

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

на 2 або ж додавання 5n.

Розділ 5

§ 37

15 of 35

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

ПРИКЛАД 1. Нехай дано послідовність із нулів та одиниць і потрібно з’ясувати, чи є там хоч одна одиниця. Яку складність матиме алгоритм розв’язання цієї задачі?

Розв’язання. Нехай n — кількість символів у послідовності. Алгоритм буде послідовно перевіряти, чи немає одиниці в поточному місці заданої послідовності, а потім рухатися далі, поки вхід не скінчиться. Оскільки одиниця дійсно може бути тільки одна, для отримання точної відповіді на це питання в гіршому випадку доведеться перевірити всі n символів входу. Таким чином, алгоритм має складність O(n), іншими словами, він лінійний.

Розділ 5

§ 37

16 of 35

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

ПРИКЛАД 2. Проаналізуємо програму для визначення кількості додатних елементів у кожному рядку масиву tabl[n, n].

for i in range(n): # Зовнішній цикл по рядках

k = 0

for j in range(n):

if tabl[i][j]>0: k = k+1

print('B', i, '-тому рядку таких елементів ', k)

Розділ 5

§ 37

17 of 35

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

У цьому алгоритмі змінна і змінюється від 1 до n. При кожній зміні і змінна j теж змінюється від 1 до n.

Під час кожної з n ітерацій зовнішнього циклу внутрішній цикл теж виконується n разів. Загальна кількість ітерацій внутрішнього циклу дорівнює n*n. Це визначає складність алгоритму O(n²).

Розділ 5

§ 37

18 of 35

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

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

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

Розділ 5

§ 37

19 of 35

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

ПРИКЛАД 3. Алгоритм послідовного пошуку елемента в масиві. Сутність методу послідовного пошуку полягає в тому, що елементи масиву послідовно порівнюються із певним значенням (ключем) пошуку.

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

Розділ 5

§ 37

20 of 35

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

Розглянемо випадок, коли елементи масиву не повторюються. Оскільки наявність та місцезнаходження елемента наперед невідомі, то пошук елемента масиву

a = [23, 12, 3, 45, 6, 17, 8, 4, 21, 81]

k = 8

i = 0

n = 10

while a[i] != k and i<n–1:

i = i+1

if i<n–1 or a[n–1] == k: print(i)

else: print('No')

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

Розділ 5

§ 37

21 of 35

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

Очевидно, що кількість елементарних операцій прямо пропорційна кількості порівнянь a[i] ≠ k. У найгіршому випадку з ключем порівнюються всі елементи масиву, тоді кількість перевірок дорівнює n.

Звідси найбільший час пошуку t є лінійною функцією від кількості елементів масиву, алгоритм має лінійну складність O(n).

Розділ 5

§ 37

22 of 35

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

Перевагою методу простого пошуку є його простота та наочність.

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

Можна спростити алгоритм, позбувшись перевірки номера (i <= n) за рахунок збільшення масиву на один елемент у кінці, значення якого буде рівним k (так званий бар’єр).

Розділ 5

§ 37

23 of 35

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

Додаткові операції з установки й зняття бар’єра

a = [23, 12, 3, 45, 6, 17, 8, 4, 21, 81]

k = 8

a = a+[k]

i = 0

n = 10

while a[i] != k:

i = i+1

if i == n: print('No')

else: print(i)

del(a[n])

print(a)

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

Розділ 5

§ 37

24 of 35

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

ПРИКЛАД 4. Алгоритм двійкового пошуку елемента в масиві. В упорядкованому масиві процес пошуку елемента можна значно прискорити, застосувавши метод бінарного пошуку.

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

Розділ 5

§ 37

25 of 35

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

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

Якщо ключ більший за центральний елемент

то елемент знайдений

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

Якщо елемент дорівнює ключу

то процес поділу й аналізу продовжується у правій частині масиву

інакше — у лівій частині

Розділ 5

§ 37

26 of 35

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

a = [23, 12, 3, 45, 6, 7, 8, 4, 21, 81]

a.sort()

k = 8

mid = len(a) // 2

low = 0

high = len(a)–1

while a[mid] != k and low <= high:

if k > a[mid]:

low = mid+1

else:

high = mid–1

mid = (low+high) // 2

if low > high: print("No value")

else: print("ID = ", mid)

Розділ 5

§ 37

27 of 35

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

Цей метод дуже ефективний, оскільки, наприклад, для масиву з 1000 елементів,

результат визначається навіть у гіршому випадку після 10 кроків циклу

тоді як для методу послідовного пошуку в середньому потрібно буде 500 кроків.

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

Розділ 5

§ 37

28 of 35

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

ПРИКЛАД 5. Оцінимо складність алгоритму сортування бульбашкою.

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

Розділ 5

§ 37

29 of 35

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

Розглянемо найгірший випадок для цього алгоритму — масив відсортовано у зворотному порядку.

Для сортування доведеться виконати n проходів масивом і n перестановок на кожному проході, тобто зробити n*n операцій порівняння й перестановок. Отже, складність цього алгоритму може оцінюватись як О(n²).

Розділ 5

§ 37

30 of 35

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

Знаючи це, ми можемо приблизно зрозуміти, які обсяги даних можна обробляти за цим алгоритмом, а які — ні.

Наприклад, для сортування 1000 елементів алгоритму в гіршому випадку знадобиться 1 секунда, але сортування 100 000 елементів чекати доведеться майже 3 години.

Розділ 5

§ 37

31 of 35

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

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

Адель Голдберг — американська вчена в галузі інформатики, відома своєю роботою у галузі об’єктно-орієнтованого програмування і графічних інтерфейсів та розробкою мови програмування Smalltalk.

Цікавинка

Розділ 5

§ 37

32 of 35

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

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

Дано послідовність з n символів і потрібно з’ясувати, чи є там хоч один символ А. Яку складність матиме алгоритм розв’язання цієї задачі?

При яких розмірах вхідних даних краще використати для пошуку елемента алгоритм послідовного пошуку? Алгоритм двійкового пошуку?

Яку складність має алгоритм сортування масиву вибором найбільшого елемента?

Розділ 5

§ 37

33 of 35

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

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

§ 37, с. 223-229

Розділ 5

§ 37

34 of 35

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

Сторінка

228-229

Розділ 5

§ 37

35 of 35

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

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

Урок 64

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

teach-inf.com.ua

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

Бондаренко О.О. та ін.