Big O та асимптотичний аналіз: як оцінити складність алгоритмів

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

Навіщо взагалі оцінювати час роботи алгоритму

Здавалося б, можна просто запустити код і заміряти час. Але з цим є проблеми:

• на різних машинах час роботи буде різним;

• потрібних даних (тих, на яких код працюватиме в проді) під рукою може не бути;

• деякі алгоритми працюють годинами або днями — не назапускаєшся;

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

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

Крок 1. Рахуємо елементарні операції

За елементарні операції можна взяти арифметику (+, -, *, /), порівняння (<, >, ==, …) та присвоєння (a[0] = 3). Важливо рахувати не рядки коду, а те, як конструкції реально працюють у мові. Наприклад, у Python зріз array[3:10] копіює ділянку масиву, тобто це не одна операція, а стільки, скільки елементів у зрізі. Найзручніше рахувати найдорожчу операцію. Нехай це умовний виклик apicall(), і нас цікавить, скільки разів він виконається залежно від n.

Простий цикл:

for (i = 4; i < n + 42; i += 2)
    apicall();

Крок циклу — 2, тому кількість викликів приблизно ((n + 42) − 4) / 2 = (n + 38) / 2. Це лінійна залежність — Θ(n): збільшили n у 10 разів, кількість викликів теж зросла приблизно в 10 разів.

Цикл із множенням:

for (i = 10; i < n + 5; i *= 3)
    apicall();

Тут i не додається, а множиться на 3. Цикл зупиниться, коли 10 · 3ᵏ ≥ n + 5, тобто після приблизно log₃(n) кроків. Кожного разу, коли лічильник множиться (чи ділиться) на константу, ви майже напевно бачите O(log n).

Вкладені цикли:

for (i = 0; i < n; ++i)
    for (j = 0; j < n; j += 2)
        apicall();

Зовнішній цикл — n ітерацій, внутрішній — n/2. Разом n · n/2 = n²/2 викликів, тобто Θ(n²). Загальне правило: вкладені цикли перемножуються.

Крок 2. Worst-case, best-case і average-case

Один і той самий алгоритм на різних входах однакового розміру може працювати по-різному. Тому розрізняють три випадки:

• worst-case — найбільша кількість кроків серед усіх входів розміру n (найпесимістичніша оцінка, і саме її дають найчастіше);

• best-case — найменша кількість кроків;

• average-case — усереднення по всіх входах розміру n.

На практиці найважливіший — worst-case: він гарантує, що гірше не буде.

Крок 3. Чому точні формули незручні

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

T(n) = 12754·n² + 4353·n + 834·log n + 13546

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

Крок 4. Big O нотація: формальне визначення

Big O відкидає різницю між множенням на константу й додаванням константи. Формально:

• f(n) = O(g(n)) — g(n) є верхньою межею: існують константи c і n₀, такі, що f(n) ≤ c·g(n) для всіх n ≥ n₀.

• f(n) = Ω(g(n)) — g(n) є нижньою межею: f(n) ≥ c·g(n) для всіх n ≥ n₀.

• f(n) = Θ(g(n)) — g(n) є одночасно верхньою і нижньою межею. Це найточніша, «затиснута» оцінка.

Малі n ігноруємо: нікого не цікавить, хто швидше сортує 6 елементів. Цікаво, хто швидший на 10 000 чи 1 000 000. Через це запис виглядає незвично, але коректно: наприклад, n² = O(n³) — бо n² дійсно є однією з функцій, обмежених зверху n³. А ще будь-яка константа — це O(1): і 179, і 10¹⁰⁰ — обидва O(1).

Практичний наслідок: усі суперечки про те, скільки операцій у swap чи рахувати присвоєння окремо від порівнянь, відпадають — вони міняють відповідь лише на константу, а отже, на асимптотику не впливають.

Основні класи складності

Big O	Назва	Типовий приклад
O(1)	константна	доступ до елемента масиву за індексом
O(log n)	логарифмічна	бінарний пошук
O(n)	лінійна	прохід по масиву
O(n log n)	лінійно-логарифмічна	швидкі сортування (merge sort, heap sort)
O(n²)	квадратична	сортування бульбашкою, вкладені цикли
O(2ⁿ)	експоненційна	наївний перебір підмножин
O(n!)	факторіальна	перебір усіх перестановок

Три прості сортування — бульбашкою, вибором і вставками — квадратичні, O(n²). А сортування підрахунком працює за O(n + m) і, якщо m ≤ n, стає лінійним O(n).

Розбір рекурсії

Лінійна рекурсія з циклом:

def f(n):
    if n == 0:
        return
    for i in range(n):
        apicall()
    f(n - 1)

На глибині 0 — n викликів, на глибині 1 — n−1, і так далі. Разом n + (n−1) + … + 1 = n(n+1)/2, тобто Θ(n²) за часом. А стек викликів заглиблюється на n рівнів — це Θ(n) пам'яті. Час і пам'ять — різні речі, оцінюйте їх окремо.

Розгалуження навпіл:

def f(n):
    if n == 0:
        return
    apicall()
    f(n // 2)
    f(n // 2)

Кількість викликів на кожному рівні дерева подвоюється, а рівнів — log₂ n + 1. Разом 1 + 2 + 4 + … + n = 2n − 1, тобто Θ(n). Подвоєння на кожному рівні не завжди означає експоненту — тут воно компенсується тим, що n ділиться на 2.

Наївний Фібоначчі — обережно:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Кожен виклик породжує два нові, тому час є експоненційним. Часто пишуть O(2ⁿ) — це коректна верхня межа, але не точна. Насправді кількість викликів дорівнює рівно 2·Fib(n+1) − 1, а це росте як Θ(φⁿ), де φ ≈ 1.618 — золотий переріз. Для n = 20 це 21 891 виклик проти 2 097 151 за оцінкою 2ⁿ — різниця майже в сто разів. Мораль: O(2ⁿ) як верхня межа — ок, але точна асимптотика тут φⁿ.

Практичне правило

Щоб швидко оцінити складність, знайдіть найглибше вкладене місце й порахуйте, скільки разів воно виконується:

• один цикл до n → O(n);

• цикл у циклі, обидва до n → O(n²);

• лічильник множиться/ділиться на константу → додається множник log n;

• рекурсія, що ділить задачу навпіл і робить лінійну роботу → часто O(n log n).

Пам'ятайте: константи й молодші доданки викидаємо. (5n² − 5n + 4)/2 — це просто O(n²).

Часті питання (FAQ)

Що таке Big O нотація простими словами? Це спосіб описати, як швидко росте час (або пам'ять) роботи алгоритму зі збільшенням розміру входу, ігноруючи константи й дрібні деталі. Замість точної формули отримуємо клас зростання: лінійний, квадратичний, логарифмічний тощо.

Чим відрізняються O, Θ і Ω? O — верхня межа («не гірше ніж»), Ω — нижня межа («не краще ніж»), Θ — і те, й інше одночасно (найточніша оцінка). На практиці найчастіше говорять про O у worst-case.

Що означає O(1), O(n) і O(n²)? O(1) — час не залежить від розміру входу. O(n) — росте пропорційно n. O(n²) — при збільшенні n у 10 разів час зростає приблизно в 100 разів.

Чому асимптотика ігнорує константи? Бо константи залежать від мови, компілятора й заліза, а не від самого алгоритму. Код на C, що вдвічі швидший за той самий алгоритм на Java, — це той самий алгоритм. Big O порівнює алгоритми, а не реалізації.

Як оцінити складність вкладених циклів? Перемножте кількість ітерацій. Два вкладені цикли до n дають O(n²), три — O(n³). Якщо внутрішній цикл залежить від зовнішнього індексу — рахуйте суму (наприклад, 1 + 2 + … + n = n(n+1)/2 = O(n²)).