Складність алгоритмів — це міра ефективності алгоритму, що описує, скільки часу та пам’яті потрібно для його виконання залежно від розміру вхідних даних.
Вона допомагає порівнювати алгоритми незалежно від конкретної реалізації чи апаратного забезпечення.
🔍 Коротке визначення #
Складність алгоритму — це функція, що виражає залежність використаних ресурсів (часу, пам’яті) від розміру входу $n$.
🧩 Види складності #
- Часова складність (Time Complexity) — кількість операцій, необхідних для завершення алгоритму.
- Просторова складність (Space Complexity) — обсяг пам’яті, який споживає алгоритм.
- Амортизована складність (Amortized Complexity) — середня складність операцій при багатьох повтореннях (наприклад, у динамічних структурах даних).
🧮 Асимптотичні позначення #
Для оцінки зростання складності при великих $n$ використовують спеціальні нотації:
$$
O(g(n)) \quad — \text{верхня межа (Big-O)}
$$
$$
\Omega(g(n)) \quad — \text{нижня межа}
$$
$$
\Theta(g(n)) \quad — \text{точна асимптотична оцінка}
$$
Наприклад, якщо час роботи алгоритму пропорційний $$n^2$$, то
$$T(n) = O(n^2)$$
📈 Типові приклади часової складності #
| Тип алгоритму | Складність | Приклад |
|---|---|---|
| Константна | $$O(1)$$ | доступ до елемента масиву |
| Логарифмічна | $$O(\log n)$$ | бінарний пошук |
| Лінійна | $$O(n)$$ | лінійний пошук |
| Лінійно-логарифмічна | $$O(n \log n)$$ | Merge Sort |
| Квадратична | $$O(n^2)$$ | Bubble Sort |
| Кубічна | $$O(n^3)$$ | множення матриць |
| Експоненційна | $$O(2^n)$$ | перебір усіх комбінацій |
| Факторіальна | $$O(n!)$$ | задачі з перестановками |
🧠 Найгірший, середній і найкращий випадок #
Для деяких алгоритмів складність залежить від структури даних:
- Найгірший випадок (Worst-case): максимальний час виконання, наприклад $$O(n^2)$$ для Quick Sort.
- Середній випадок (Average-case): очікувана складність при випадкових даних, $$O(n \log n)$$ для Quick Sort.
- Найкращий випадок (Best-case): мінімальний час виконання, наприклад $$O(n)$$, коли дані вже відсортовані.
⚙️ Аналіз складності #
- Рахуємо кількість базових операцій у найгіршому сценарії.
- Відкидаємо константи та незначні доданки.
- Визначаємо асимптотичну поведінку.
Приклад:
$$T(n) = 5n^2 + 3n + 20 \Rightarrow O(n^2)$$
📚 Класи складності #
У теорії алгоритмів виділяють логічні класи задач:
- P — задачі, що розв’язуються за поліноміальний час.
- NP — задачі, для яких можна перевірити розв’язок за поліноміальний час.
- NP-повні (NP-complete) — найскладніші задачі у NP.
- NP-тяжкі (NP-hard) — задачі не простіші за NP-повні.
Відкрите питання: чи $$P = NP$$?
⚖️ Навіщо оцінювати складність #
- для порівняння ефективності алгоритмів;
- для вибору найкращого методу під конкретний обсяг даних;
- для оптимізації програм та обчислювальних ресурсів.
🧩 Зв’язок з іншими поняттями #
📚 Джерела #
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS)
- Knuth, D. The Art of Computer Programming
- Sedgewick, R. Algorithms
- Sipser, M. Introduction to the Theory of Computation
🏷️ Категорії: #
Алгоритми • Data Science • Математика і статистика • Штучний інтелект
