← O(2ⁿ) — експоненціальна складність
docs: English JsonRpcBundle docs, REST and MCP Bundle sections, package cards
uk/articles/from-tg/series/algorithm-complexity/o-2n.md
новий файл +26
−0
1
+
# O(2ⁿ) — експоненціальна складність
2
+
3
+
Це вже абсолютна прірва. Зі зростанням обсягу вхідних даних час виконання алгоритму росте дуже швидко. Подвоїли вхід — подвоїли час. І з кожним наступним збільшенням ситуація тільки погіршується.
4
+
5
+
## Приклад: обчислення чисел Фібоначчі наївним рекурсивним методом
6
+
7
+
```php
8
+
function naiveFibonacci($n) {
9
+
if ($n <= 1) return $n;
10
+
return naiveFibonacci($n - 1) + naiveFibonacci($n - 2);
11
+
}
12
+
```
13
+
14
+
На перший погляд — все просто. Але з кожним викликом функція породжує два нових. І так далі, і далі… Пам’ятаєш кроликів Фібоначчі? Ось вони, множаться як божевільні.
15
+
16
+
У реальних проєктах рекурсивні алгоритми з експоненціальною складністю трапляються рідко, бо майже завжди є ефективніший підхід (динамічне програмування, кешування результатів).
17
+
18
+
:::warning
19
+
O(2ⁿ) — це червоний прапорець. Якщо ви бачите щось подібне у продакшені — час бити на сполох і шукати оптимізацію.
20
+
:::
21
+
22
+
← [Попередня: O(n³) — кубічна складність](/articles/from-tg/series/algorithm-complexity/o-n3) · [Уся серія](/articles/from-tg/series/algorithm-complexity) · [Наступна: O(n!) — факторіальна складність →](/articles/from-tg/series/algorithm-complexity/o-n-factorial)
23
+
24
+
---
25
+
26
+
*Вперше опубліковано в Telegram-каналі [«Створений щоб помирати»](https://t.me/php_while_true/48) 26.06.2025.*