Оцінка складності алгоритмів¶

Навіщо потрібна складність алгоритму¶

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

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

Приклад

Два алгоритми пошуку елемента в масиві:

Лінійний пошук — перевіряємо кожен елемент по черзі
Бінарний пошук — відкидаємо половину масиву на кожному кроці

Для масиву з 10 елементів обидва працюють майже миттєво. Але для масиву з 1 000 000 елементів лінійний пошук може потребувати мільйон перевірок, а бінарний — лише ~20.

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

Інтуїтивне розуміння складності¶

Основна ідея¶

Складність алгоритму — це характеристика того, як зростає кількість дій, які виконує алгоритм, коли зростає розмір вхідних даних.

Нехай:

\(n\) — розмір вхідних даних (наприклад, кількість елементів масиву)
\(T(n)\) — кількість елементарних операцій, які виконує алгоритм

Тоді нас цікавить не стільки точне значення \(T(n)\), скільки загальний характер її росту.

Приклад: доступ до елемента масиву — \(O(1)\)¶

int x = v[5]; // One operation, regardless of array size

Кількість дій не залежить від розміру масиву. Така операція має сталий час: \(O(1)\).

Приклад: лінійний пошук — \(O(n)\)¶

template<typename T>
int linear_search(vector<T>& v, T value) {
    for (int i = 0; i < v.get_size(); ++i) {
        if (v[i] == value) {
            return i;
        }
    }
    return -1;
}

У найгіршому випадку потрібно переглянути всі \(n\) елементів. Складність — лінійна: \(O(n)\).

Приклад: подвійний цикл — \(O(n^2)\)¶

// Check all pairs of elements
for (int i = 0; i < v.get_size(); ++i) {
    for (int j = 0; j < v.get_size(); ++j) {
        // Some O(1) operation
    }
}

Зовнішній цикл виконується \(n\) разів, для кожної ітерації внутрішній цикл також виконується \(n\) разів. Загальна кількість дій: \(n \cdot n = n^2\). Складність — квадратична: \(O(n^2)\).

Приклад: бінарний пошук — \(O(\log n)\)¶

Якщо масив відсортований, можна не переглядати його повністю, а кожного разу відкидати половину елементів:

template<typename T>
int binary_search(vector<T>& v, T value) {
    int left = 0;
    int right = v.get_size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (v[mid] == value) return mid;
        if (v[mid] < value) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Кожна ітерація зменшує область пошуку вдвічі. Після \(k\) ітерацій залишається \(n / 2^k\) елементів. Алгоритм зупиняється, коли \(n / 2^k = 1\), тобто \(k = \log_2 n\). Складність — логарифмічна: \(O(\log n)\).

Порівняльна таблиця¶

\(n\)	\(O(1)\)	\(O(\log n)\)	\(O(n)\)	\(O(n \log n)\)	\(O(n^2)\)
10	1	~3	10	~33	100
100	1	~7	100	~664	10 000
1 000	1	~10	1 000	~9 966	1 000 000
10 000	1	~13	10 000	~132 877	100 000 000

Ця таблиця наочно показує, що при великих \(n\) різниця між порядками росту стає критичною.

Чому нас не цікавить точна кількість операцій¶

Припустимо, що для одного алгоритму \(T(n) = 3n + 5\), а для іншого \(T(n) = 100n + 20\). Другий виконує більше дій, але обидві функції ростуть лінійно. При дослідженні складності нас цікавить саме тип росту, а не точні константи.

Чому?

Константи залежать від конкретного комп'ютера, компілятора, оптимізацій
При великих \(n\) тип росту домінує над константами
Алгоритм з \(T(n) = 1000n\) завжди обжене алгоритм з \(T(n) = n^2\) при достатньо великому \(n\)

Тому:

\(2n + 3\) має той самий порядок росту, що й \(n\)
\(5n^2 + 10n + 1\) має той самий порядок росту, що й \(n^2\)
\(7 \log n + 100\) має той самий порядок росту, що й \(\log n\)

Формальне означення Big-O¶

Інтуїтивного розуміння недостатньо, якщо ми хочемо міркувати строго. Тому вводять математичне означення.

Означення¶

Означення Big-O

Нехай \(f(n)\) і \(g(n)\) — невід'ємні функції, визначені для всіх достатньо великих \(n\).

Кажуть, що \(f(n) = O(g(n))\), якщо існують такі сталі \(C > 0\) і \(n_0\), що для всіх \(n \geq n_0\) виконується нерівність:

\[0 \leq f(n) \leq C \cdot g(n)\]

Інтуїтивний зміст¶

\(f(n) = O(g(n))\) означає: функція \(f(n)\) не росте швидше, ніж \(g(n)\), з точністю до сталого множника. Це верхня оцінка росту.

Приклад: довести, що \(3n + 5 = O(n)\)¶

Доведення. Потрібно знайти \(C > 0\) і \(n_0\), такі що для всіх \(n \geq n_0\):

\[3n + 5 \leq C \cdot n\]

Для \(n \geq 5\) маємо \(5 \leq n\), тому:

\[3n + 5 \leq 3n + n = 4n\]

Отже, можна взяти \(C = 4\), \(n_0 = 5\).

\[\forall n \geq 5: \quad 3n + 5 \leq 4n\]

Тому \(3n + 5 = O(n)\). \(\square\)

Приклад: довести, що \(n^2 + 3n + 1 = O(n^2)\)¶

Доведення. Для \(n \geq 3\):

\[n^2 + 3n + 1 \leq n^2 + n \cdot n + n^2 = 3n^2\]

(бо \(3n \leq n^2\) при \(n \geq 3\) і \(1 \leq n^2\) при \(n \geq 1\))

Отже, \(C = 3\), \(n_0 = 3\). \(\square\)

Означення Omega (\(\Omega\))¶

Означення¶

Означення Omega

Кажуть, що \(f(n) = \Omega(g(n))\), якщо існують такі сталі \(c > 0\) і \(n_0\), що для всіх \(n \geq n_0\):

\[0 \leq c \cdot g(n) \leq f(n)\]

Інтуїтивний зміст¶

\(f(n) = \Omega(g(n))\) означає: функція \(f(n)\) росте не повільніше, ніж \(g(n)\). Це нижня оцінка росту.

Приклад: \(3n + 5 = \Omega(n)\)¶

Для всіх \(n \geq 1\):

\[3n + 5 \geq 3n \geq 1 \cdot n\]

Отже, \(c = 1\), \(n_0 = 1\). \(\square\)

Означення Theta (\(\Theta\))¶

Означення¶

Означення Theta

Кажуть, що \(f(n) = \Theta(g(n))\), якщо одночасно \(f(n) = O(g(n))\) і \(f(n) = \Omega(g(n))\).

Тобто існують сталі \(c > 0\), \(C > 0\) і \(n_0\), що для всіх \(n \geq n_0\):

\[0 \leq c \cdot g(n) \leq f(n) \leq C \cdot g(n)\]

Інтуїтивний зміст¶

\(f(n) = \Theta(g(n))\) означає: функції \(f(n)\) і \(g(n)\) мають однаковий порядок росту. Це точна асимптотична оцінка.

Приклад: \(3n + 5 = \Theta(n)\)¶

Оскільки ми вже показали, що \(3n + 5 = O(n)\) і \(3n + 5 = \Omega(n)\), то \(3n + 5 = \Theta(n)\).

Зведена таблиця позначень¶

Позначення	Зміст	Аналогія
\(f(n) = O(g(n))\)	\(f\) росте не швидше ніж \(g\)	\(f \leq g\) (верхня межа)
\(f(n) = \Omega(g(n))\)	\(f\) росте не повільніше ніж \(g\)	\(f \geq g\) (нижня межа)
\(f(n) = \Theta(g(n))\)	\(f\) і \(g\) ростуть однаково	\(f \approx g\) (точна оцінка)

Що використовують на практиці

У базовому курсі найчастіше використовують \(O(\ldots)\) — верхню оцінку. Але важливо розуміти, що це лише одна сторона. Коли кажуть "алгоритм працює за \(O(n \log n)\)", зазвичай мають на увазі, що це також \(\Theta(n \log n)\) — точна оцінка.

Оцінка складності фрагментів програм¶

Правило 1: послідовні інструкції¶

int a = b + c; // O(1)
int d = a + 1; // O(1)

Складність: \(O(1) + O(1) = O(1)\).

Правило 2: один цикл¶

for (int i = 0; i < n; ++i) {
    // O(1) operation
}

Складність: \(O(n)\).

Правило 3: вкладені цикли¶

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        // O(1) operation
    }
}

Складність: \(O(n) \cdot O(n) = O(n^2)\).

Правило 4: цикл із поділом навпіл¶

int x = n;
while (x > 1) {
    x = x / 2;
}

На кожній ітерації \(x\) зменшується вдвічі: \(n, n/2, n/4, \ldots, 1\). Кількість ітерацій: \(\log_2 n\). Складність: \(O(\log n)\).

Правило 5: комбінація послідовних фрагментів¶

for (int i = 0; i < n; ++i) { /* ... */ }  // O(n)

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) { /* ... */ }  // O(n^2)
}

Загальна складність: \(O(n) + O(n^2) = O(n^2)\). Менший доданок поглинається більшим.

Правило 6: залежні цикли¶

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        // O(1) operation
    }
}

Внутрішній цикл виконується \(0 + 1 + 2 + \ldots + (n-1)\) разів. Це сума арифметичної прогресії:

\[\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2} = \frac{n^2 - n}{2}\]

Складність: \(O(n^2)\).

Правило 7: цикл з множенням¶

int x = 1;
while (x < n) {
    x = x * 2;
}

Значення \(x\): \(1, 2, 4, 8, \ldots, n\). Кількість ітерацій: \(\log_2 n\). Складність: \(O(\log n)\).

Рекурсивна складність¶

У лекції про рекурсію ми бачили, що рекурсивні функції викликають самі себе. Як оцінити їх складність?

Рекурентне співвідношення¶

Складність рекурсивної функції описується рекурентним співвідношенням — формулою, де \(T(n)\) виражається через \(T\) від менших значень.

Приклад 1: рекурсивна сума масиву¶

template<typename T>
T recursive_sum(vector<T>& v, int index) {
    if (index >= v.get_size()) return 0;
    return v[index] + recursive_sum(v, index + 1);
}

Рекурентне співвідношення: \(T(n) = T(n-1) + O(1)\), базовий випадок \(T(0) = O(1)\).

Розкриваємо: \(T(n) = T(n-1) + 1 = T(n-2) + 2 = \ldots = T(0) + n = O(n)\).

Приклад 2: бінарний пошук¶

template<typename T>
int binary_search(vector<T>& v, T value, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (v[mid] == value) return mid;
    if (v[mid] > value) return binary_search(v, value, left, mid - 1);
    return binary_search(v, value, mid + 1, right);
}

На кожному кроці розмір задачі зменшується вдвічі, і виконується лише один рекурсивний виклик:

\[T(n) = T(n/2) + O(1)\]

Розкриваємо: \(T(n) = T(n/2) + 1 = T(n/4) + 2 = \ldots = T(1) + \log_2 n = O(\log n)\).

Приклад 3: merge sort (дерево рекурсії)¶

Merge sort ділить масив навпіл і робить два рекурсивні виклики, а потім зливає результати за \(O(n)\):

\[T(n) = 2T(n/2) + O(n)\]

Для аналізу використаємо дерево рекурсії:

flowchart TB
    L0["Рівень 0: один масив розміру n\nРобота: O(n)"]
    L1["Рівень 1: два масиви по n/2\nРобота: 2 × O(n/2) = O(n)"]
    L2["Рівень 2: чотири масиви по n/4\nРобота: 4 × O(n/4) = O(n)"]
    L3["...\nРобота на кожному рівні: O(n)"]
    LK["Рівень log₂n: n масивів по 1\nРобота: O(n)"]

    L0 --> L1 --> L2 --> L3 --> LK

На кожному рівні сумарна робота — \(O(n)\). Кількість рівнів — \(\log_2 n\) (бо на кожному рівні розмір задачі зменшується вдвічі).

Загальна складність:

\[T(n) = O(n) \cdot \log_2 n = O(n \log n)\]

Приклад 4: наївні числа Фібоначчі¶

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Рекурентне співвідношення: \(T(n) = T(n-1) + T(n-2) + O(1)\).

Це складніше розкрити точно, але можна показати, що \(T(n) = O(2^n)\) — експоненціальна складність. Кожен виклик породжує два нових, і дерево викликів росте як повне бінарне дерево.

Підсумок рекурсивної складності¶

Рекурентність	Приклад	Складність
\(T(n) = T(n-1) + O(1)\)	Факторіал, лінійний пошук	\(O(n)\)
\(T(n) = T(n/2) + O(1)\)	Бінарний пошук	\(O(\log n)\)
\(T(n) = 2T(n/2) + O(n)\)	Merge sort	\(O(n \log n)\)
\(T(n) = 2T(n/2) + O(1)\)	Обхід бінарного дерева	\(O(n)\)
\(T(n) = T(n-1) + T(n-2)\)	Наївний Фібоначчі	\(O(2^n)\)

Для допитливих

Існує загальна формула для рекурентностей виду \(T(n) = aT(n/b) + O(n^c)\) — Master theorem. Вона дозволяє швидко визначити складність без побудови дерева. Детальніше — у додатковому матеріалі.

Порівняння функцій за швидкістю росту¶

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

\[\lim_{n \to \infty} \frac{f(n)}{g(n)}\]

Три випадки¶

Значення границі	Що це означає
\(\lim = 0\)	\(f(n)\) росте повільніше ніж \(g(n)\)
\(\lim = c\), де \(0 < c < \infty\)	\(f(n)\) і \(g(n)\) мають однаковий порядок росту: \(f(n) = \Theta(g(n))\)
\(\lim = \infty\)	\(f(n)\) росте швидше ніж \(g(n)\)

Приклад¶

\[\lim_{n \to \infty} \frac{3n + 5}{n} = \lim_{n \to \infty} \left(3 + \frac{5}{n}\right) = 3\]

Границя — скінченна додатна стала, отже \(3n + 5 = \Theta(n)\).

Стандартна шкала росту функцій¶

\[1 \ll \log n \ll \sqrt{n} \ll n \ll n \log n \ll n^2 \ll n^3 \ll 2^n \ll n!\]

Тут символ \(\ll\) означає: "росте значно повільніше". Кожна наступна функція при великих \(n\) домінує над попередніми.

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

Важливе зауваження

Асимптотика алгоритмів — це дискретна тема: змінна \(n\) натуральна. Правило Лопіталя — інструмент математичного аналізу для неперервних функцій. Ми використовуємо його тут як допоміжний інструмент для порівняння порядків росту, розглядаючи відповідні неперервні функції.

Правило Лопіталя¶

Якщо при \(x \to \infty\) маємо невизначеність \(\frac{\infty}{\infty}\) або \(\frac{0}{0}\), то:

\[\lim_{x \to \infty} \frac{f(x)}{g(x)} = \lim_{x \to \infty} \frac{f'(x)}{g'(x)}\]

за умови, що границя справа існує.

Приклад 1: \(\log x\) vs \(x\)¶

\[\lim_{x \to \infty} \frac{\log x}{x} = \left[\frac{\infty}{\infty}\right]\]

Застосовуємо правило Лопіталя (нагадаємо: \((\log x)' = \frac{1}{x}\), \((x)' = 1\)):

\[\lim_{x \to \infty} \frac{\log x}{x} = \lim_{x \to \infty} \frac{1/x}{1} = \lim_{x \to \infty} \frac{1}{x} = 0\]

Висновок: \(\log n\) росте повільніше ніж \(n\). Записуємо: \(\log n = o(n)\).

Приклад 2: \(x^2\) vs \(2^x\)¶

\[\lim_{x \to \infty} \frac{x^2}{2^x} = \left[\frac{\infty}{\infty}\right]\]

Перше застосування Лопіталя (\((x^2)' = 2x\), \((2^x)' = 2^x \ln 2\)):

\[= \lim_{x \to \infty} \frac{2x}{2^x \ln 2} = \left[\frac{\infty}{\infty}\right]\]

Друге застосування (\((2x)' = 2\), \((2^x \ln 2)' = 2^x (\ln 2)^2\)):

\[= \lim_{x \to \infty} \frac{2}{2^x (\ln 2)^2} = 0\]

Висновок: \(n^2\) росте значно повільніше ніж \(2^n\). Записуємо: \(n^2 = o(2^n)\).

Приклад 3: \(x^k\) vs \(a^x\) (загальний результат)¶

Аналогічно можна показати, що для будь-якого натурального \(k\) і будь-якого \(a > 1\):

\[\lim_{x \to \infty} \frac{x^k}{a^x} = 0\]

Після \(k\) застосувань правила Лопіталя в чисельнику отримаємо сталу \(k!\), а в знаменнику — \(a^x (\ln a)^k \to \infty\).

Висновок: будь-яка експоненціальна функція з основою \(a > 1\) зростає швидше за будь-який многочлен:

\[n^k = o(a^n) \quad \text{при } a > 1\]

Це пояснює, чому алгоритми з експоненціальною складністю (\(O(2^n)\)) є практично непридатними для великих \(n\), навіть порівняно з \(O(n^3)\).

Позначення little-o¶

Означення little-o

\(f(n) = o(g(n))\), якщо \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\).

Це означає, що \(f(n)\) росте строго повільніше ніж \(g(n)\).

На відміну від Big-O (\(\leq\) з точністю до константи), little-o означає строго менше — без можливості рівності.

Приклади:

\(\log n = o(n)\) — логарифм строго повільніший за лінійну функцію
\(n = o(n^2)\) — лінійна строго повільніша за квадратичну
\(n^k = o(a^n)\) при \(a > 1\) — многочлен строго повільніший за експоненту

Як це пов'язано з алгоритмами¶

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

Складність	Назва	Приклад алгоритму	Практична оцінка для \(n = 10^6\)
\(O(1)\)	Константна	Доступ за індексом	1 операція
\(O(\log n)\)	Логарифмічна	Бінарний пошук	~20 операцій
\(O(n)\)	Лінійна	Лінійний пошук	\(10^6\) операцій
\(O(n \log n)\)	Лінеарифмічна	Merge sort	~\(2 \cdot 10^7\) операцій
\(O(n^2)\)	Квадратична	Bubble sort	\(10^{12}\) операцій
\(O(2^n)\)	Експоненціальна	Наївний Фібоначчі	\(\approx 10^{301\,030}\) операцій

Експоненціальна складність

При \(n = 100\) алгоритм з \(O(2^n)\) потребує \(2^{100} \approx 10^{30}\) операцій. Навіть якщо комп'ютер виконує мільярд операцій на секунду, це займе \(10^{21}\) секунд — більше ніж вік Всесвіту.

Підсумок¶

Ключові поняття¶

Поняття	Що запам'ятати
\(T(n)\)	Кількість операцій алгоритму як функція від розміру вхідних даних
\(O(g(n))\)	Верхня оцінка: \(f\) росте не швидше ніж \(g\)
\(\Omega(g(n))\)	Нижня оцінка: \(f\) росте не повільніше ніж \(g\)
\(\Theta(g(n))\)	Точна оцінка: \(f\) і \(g\) мають однаковий порядок росту
\(o(g(n))\)	\(f\) росте строго повільніше ніж \(g\)
Дерево рекурсії	Метод аналізу рекурсивної складності

Як оцінити складність: короткий алгоритм¶

Визначте, які цикли є і як вони залежать від \(n\)
Для вкладених циклів — перемножте кількість ітерацій
Для послідовних фрагментів — візьміть максимум
Для рекурсії — запишіть рекурентне співвідношення і розкрийте його
Відкиньте константи і менші доданки

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

Чому алгоритм, який працює правильно, не обов'язково є хорошим?
Чим відрізняються \(O(n)\) і \(\Theta(n)\)?
Чому \(3n + 5 = \Theta(n)\)?
Чому \(n^2\) росте швидше, ніж \(n \log n\)?
Чому \(2^n\) є значно гіршою складністю, ніж \(n^3\)?
Як за допомогою границі зрозуміти, яка з двох функцій росте швидше?

Попередня: Рекурсія | Наступна: Алгоритми сортування | Задачі: Оцінка складності

Додатково: Master theorem