O(2ⁿ) — експоненціальна складність

O(2ⁿ) — експоненціальна складність

Це вже абсолютна прірва. Зі зростанням обсягу вхідних даних час виконання алгоритму росте дуже швидко. Подвоїли вхід — подвоїли час. І з кожним наступним збільшенням ситуація тільки погіршується.

Приклад: обчислення чисел Фібоначчі наївним рекурсивним методом

function naiveFibonacci($n) {
    if ($n <= 1) return $n;
    return naiveFibonacci($n - 1) + naiveFibonacci($n - 2);
}

На перший погляд — все просто. Але з кожним викликом функція породжує два нових. І так далі, і далі… Пам’ятаєш кроликів Фібоначчі? Ось вони, множаться як божевільні.

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

O(2ⁿ) — це червоний прапорець. Якщо ви бачите щось подібне у продакшені — час бити на сполох і шукати оптимізацію.

← Попередня: O(n³) — кубічна складність · Уся серія · Наступна: O(n!) — факторіальна складність →

Вперше опубліковано в Telegram-каналі «Створений щоб помирати» 26.06.2025.