O(n!) — Факториальная сложность

Определение

Факториальная сложность — наихудший вид временной сложности, где время выполнения растет факториально от размера входных данных.

Формула

$O(n!)=O(n\times (n-1)\times (n-2)\times ...\times 2\times 1)$

$n!=1\times 2\times 3\times ...\times n$

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

• Самая медленная сложность
• Практически непригодна уже для n > 12
• Встречается при полном переборе всех перестановок
• Часто требует эвристических подходов

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

n	n!	Время (1 оп = 1 нс)	Масштаб
1	1	1 нс	мгновенно
5	120	120 нс	мгновенно
10	3,628,800	~3.6 мс	быстро
12	479,001,600	~0.5 сек	приемлемо
15	~1.3 трлн	~22 мин	медленно
20	~2.4 квинтиллиона	~77 лет	невозможно

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

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

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

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

n ≤ 10:   ✅✅✅  миллисекунды
n = 11:   ✅✅   ~40 мс
n = 12:   ✅    ~500 мс
n = 13:   ⚠️    ~6.5 сек
n = 14:   ❌    ~90 сек
n ≥ 15:   ❌❌  практически невозможно

NP-полные задачи

Многие задачи с O(n!) сложностью относятся к классу NP-полных задач:

• Задача коммивояжера (TSP)
• Задача о рюкзаке (полная версия)
• Раскраска графа
• Задача выполнимости (SAT)

Для них не известно полиномиальных алгоритмов точного решения!

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

✅ Почти всегда можно найти приближенное решение ✅ Используйте эвристики для NP-полных задач ✅ Backtracking с отсечениями может помочь ❌ Непригодно для n > 12-13 в общем случае ❌ Полный перебор перестановок — всегда O(n!)

Примеры кода

Генерация всех перестановок

function getPermutations(arr) {
  if (arr.length <= 1) {
    return [arr];
  }
 
  const result = [];
 
  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
    const remainingPermutations = getPermutations(remaining);
 
    for (const perm of remainingPermutations) {
      result.push([current, ...perm]);
    }
  }
 
  return result;
}
 
console.log(getPermutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
// Всего: 3! = 6 перестановок

Задача коммивояжера (Brute Force)

function tsp(cities, distances) {
  const n = cities.length;
  const indices = Array.from({ length: n }, (_, i) => i);
  const permutations = getPermutations(indices);
 
  let minDistance = Infinity;
  let bestRoute = null;
 
  for (const perm of permutations) {
    let distance = 0;
 
    for (let i = 0; i < n - 1; i++) {
      distance += distances[perm[i]][perm[i + 1]];
    }
    distance += distances[perm[n - 1]][perm[0]];
 
    if (distance < minDistance) {
      minDistance = distance;
      bestRoute = perm.map(i => cities[i]);
    }
  }
 
  return { route: bestRoute, distance: minDistance };
}