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

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

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

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

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

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

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

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

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

Часова складність алгоритму — характеристика

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

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

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

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

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

• Лінійну складність O(n) мають алгоритми, час виконання яких лінійно залежить від кількості вхідних даних, наприклад алгоритм пошуку найбільшого елемента в невідсортованому масиві, для чого потрібно переглянути всі n елементів масиву; алгоритм додавання/віднімання чисел із n цифр.

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

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

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

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

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

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

# Зовнішній цикл по рядках

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

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

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

ПРИКЛАД 3. Алгоритм послідовного пошуку елемента в масиві.

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

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

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

ПРИКЛАД 4. Алгоритм двійкового пошуку елемента в масиві.

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

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

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

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

ПРИКЛАД 5. Оцінимо складність алгоритму сортування бульбашкою. При виконанні алгоритму при кожному проході по масиву елементи порівнюються парами і, за необхідності, міняються місцями у заданому порядку (за зростанням або за спаданням).

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

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

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

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

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

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

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

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

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

5. Наведіть приклади алгоритмів, які мають складність О(1).

6. Наведіть приклади алгоритмів, які мають складність О(п).

Вправа 37

Скласти програму для виконання завдання.

Завдання. Визначити час роботи алгоритму залежно від розміру вхідних даних, якщо для розміру n вхідних даних час роботи алгоритму дорівнює fn) мікросекунд.

1. Створіть Python file із назвою Час роботи. Завантажте модулі tkinter, matplotlib.pyplot.

Створіть вікно програми із заголовком Час роботи. Завершіть програму оператором root.mainloop().

2. Створіть список n для збереження значень кількості вхідних даних.

Заповніть список f значеннями часу роботи алгоритму при кількості вхідних даних n[i] (в секундах), якщо 1 мікросекунда = 10^-6 секунди.

3. Додайте у вікно програми віджет lab1 класу Label.

Додайте віджет box1 класу Listbox, занесіть до списку box1 значення списку n:

4. Додайте у вікно програми віджет lab2 класу Label для виведення напису Час роботи і віджет box2 класу Listbox, до списку якого занесіть значення списку f.

5. Додайте у вікно віджет btn1 класу Button.

6. Опишіть функцію btn1_cl(), призначену для побудови графіка за значеннями елементів масивів n, f.

Випробуйте роботу програми.

Комп’ютерне тестування

Виконайте тестове завдання 37 з автоматичною перевіркою результату.

 

 

Це матеріал з підручника Інформатика 9 клас Бондаренко 2022