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

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

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

О-нотація

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

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

Насправді все дуже просто. Спробуємо пояснити на прикладі, скажімо, алгоритму сортування бульбашкою.  

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

Оцінимо складність цього алгоритму.  

Припустимо, що на вхід подається повністю відсортований масив з 10 елементів, тобто n=10. Ми порівнюємо всі пари елементів від початку до кінця, змінювати нічого не потрібно. Таким чином, за 10 операцій порівняння на виході ми отримуємо відсортований масив. Здається все супер, алгоритм працює, і доволі швидко!  

А що як подати на вхід масив, відсортований у зворотньому порядку? Алгоритм цьому навряд чи зрадіє. Йому доведеться виконати 10 проходів масивом і 10 перестановок на кожному проході, тобто зробити 100 операцій порівняння й перестановок.  

Це найгірший випадок для цього алгоритму, і як ми бачимо, за таких умов доведеться виконати n² операцій. Виходить, що складність цього алгоритму може оцінюватись як О(n²), тобто функція, яку ми шукаємо, матиме такий вигляд: g(n)=n². Запис О(n²) як раз і свідчить про те, що, в гіршому випадку, для сортування масиву, який складається з n елементів, нашому алгоритму треба здійснити n² операцій.  

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

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

Звідси можемо зробити висновок, що варто пошукати інший алгоритм :)  

Оцінка кращого та середнього випадку  

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

Для позначення оцінки найкращого випадку використовується Ω-нотація, а для оцінки середнього випадку — Θ-нотація.  

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

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

Θ(n²) – у середньому випадку, коли дані перемішані у випадковому порядку, обчислювальна складність алгоритму також буде квадратично залежати від кількості елементів. 

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

Підведемо підсумки 

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

P.S. Якщо ця стаття була для вас корисною, ставте 👍 і поділіться нею з друзями!