O(2ⁿ) — Экспоненциальная сложность

Определение

Экспоненциальная сложность означает, что время выполнения удваивается с каждым увеличением размера входных данных на единицу.

Формула

$O(2^n)$

Характеристики

• Время растет экспоненциально
• Каждый дополнительный элемент удваивает время
• Практически непригодно для больших n
• Часто встречается в наивных рекурсивных решениях

Рост времени выполнения

n	2^n	Время (1 оп = 1 мкс)	Масштаб
1	2	2 мкс	мгновенно
5	32	32 мкс	мгновенно
10	1,024	~1 мс	быстро
20	1,048,576	~1 сек	приемлемо
30	1,073,741,824	~18 мин	медленно
40	~1.1 трлн	~12 дней	непригодно

График сложности (логарифмическая шкала)

Операции (log₁₀)
        |
  10¹⁵  |                                 ●  O(2ⁿ)
        |                              ●
  10¹²  |                           ●
        |                        ●
  10⁹   |                     ●
        |                  ●
  10⁶   |               ●
        |            ●
  10³   |     ● ● ●  O(n³)
        | ● ●●  O(n²)
   10   |●  O(n)
        |
    1   +-------------------------------------------->
          5   10   15   20   25   30   35       n

Практические ограничения

Максимально допустимые размеры:

• n = 20: выполнимо за секунды ✅
• n = 30: выполнимо за минуты ⚠️
• n = 40: выполнимо за часы/дни ❌
• n > 50: практически невыполнимо ❌❌

Важно помнить

✅ Часто можно оптимизировать до O(n) или O(n²) ✅ Используйте мемоизацию для рекурсивных решений ❌ Непригодно для n > 25-30 ❌ Наивные рекурсивные решения часто дают O(2ⁿ)

Примеры кода

Рекурсивный Фибоначчи (наивный)

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
 
  return fibonacci(n - 1) + fibonacci(n - 2);
}
 
console.log(fibonacci(5));  // 5
console.log(fibonacci(10)); // 55
console.log(fibonacci(40)); // Очень долго!

Генерация всех подмножеств

function getAllSubsets(arr) {
  const result = [[]];
 
  for (const element of arr) {
    const length = result.length;
 
    for (let i = 0; i < length; i++) {
      result.push([...result[i], element]);
    }
  }
 
  return result;
}
 
console.log(getAllSubsets([1, 2, 3]));
// Всего: 2³ = 8 подмножеств