Коли ми пишемо код, ми хочемо, щоб він був не лише правильним, але й швидким. Але як виміряти "швидкість"? Секундомір не допоможе, адже час виконання залежить від потужності комп'ютера, мови програмування та навіть навантаження на систему в конкретний момент. Нам потрібен універсальний інструмент для аналізу, і цей інструмент — асимптотична нотація. Вона дозволяє описати, як зростає час виконання алгоритму зі збільшенням обсягу вхідних даних.

Існує три основних "виміри" цієї нотації: Big O, Big Omega (Ω) і Big Theta (Θ). Разом вони дають повну картину поведінки алгоритму.

Big O: Верхня межа Найчастіше ви будете зустрічати саме нотацію Big O ($O$). Вона описує найгірший сценарій. Якщо ми кажемо, що алгоритм має складність $O(n^2)$, це означає, що час його виконання зростає не швидше, ніж квадрат від кількості вхідних елементів $n$. Це гарантія: ваш алгоритм ніколи не буде працювати повільніше, ніж ця межа, при достатньо великих $n$.

Big Omega: Нижня межа Нотація Big Omega ($\\\Omega$) — це протилежність. Вона описує найкращий сценарій, встановлюючи нижню межу часу виконання. Якщо алгоритм має складність $\\\Omega(n)$, це означає, що він ніколи не виконається швидше, ніж лінійно відносно розміру вхідних даних. Це мінімальний обсяг роботи, який доведеться виконати.

Big Theta: Точна межа Нотація Big Theta ($\\\\Theta$) — це найточніша оцінка. Вона використовується, коли верхня і нижня межі збігаються. Якщо алгоритм має складність $\\\\Theta(n)$, це означає, що його час виконання в найкращому та найгіршому випадках зростає однаково — лінійно. Це ідеальний сценарій для аналізу, оскільки він дає найчіткіше уявлення про поведінку алгоритму.

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

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

Розв'язувати такі співвідношення вручну може бути складно. На щастя, існує потужний інструмент — Master Theorem (основна теорема про рекуренції). Вона надає готовий рецепт для розв'язання рекурентних співвідношень певного виду.

Іноді аналіз найгіршого випадку може бути надто песимістичним. Деякі операції можуть бути дуже "дорогими", але трапляються рідко. У таких ситуаціях використовують амортизаційний аналіз (amortized analysis). Його ідея — розподілити вартість рідкісних дорогих операцій на всі інші, дешеві операції.

Уявіть динамічний масив (як ArrayList в Java або list в Python). Більшість операцій додавання елемента виконуються за константний час, $O(1)$. Але коли масив заповнюється, його потрібно розширити: створити новий, більший масив і скопіювати туди всі старі елементи. Ця операція коштує $O(n)$. Якби ми оцінювали лише найгірший випадок, то сказали б, що додавання елемента має складність $O(n)$.

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

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

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