Какие алгоритмы могут иметь сложность O(N!)?

Что такое O(N!)?

Сложность O(N!) означает, что время выполнения алгоритма растёт пропорционально факториалу от размера входных данных. Факториал N! — это произведение всех чисел от 1 до N, что даёт очень быстрый рост: 5! = 120, 10! = 3 628 800, 20! ≈ 2.43×10¹⁸.

Примеры алгоритмов

• Задача коммивояжера (TSP) полным перебором: нужно найти кратчайший маршрут, проходящий через все города ровно один раз. Количество возможных маршрутов — (N-1)!/2, что даёт O(N!).
• Генерация всех перестановок: например, вывод всех возможных перестановок массива из N элементов. Алгоритм рекурсивно перебирает все варианты.
• Задача о назначениях полным перебором: распределение N задач между N исполнителями всеми возможными способами.

Пример кода (генерация перестановок)

function permute(arr, l, r) {
  if (l === r) {
    console.log(arr);
  } else {
    for (let i = l; i <= r; i++) {
      [arr[l], arr[i]] = [arr[i], arr[l]]; // swap
      permute(arr, l + 1, r);
      [arr[l], arr[i]] = [arr[i], arr[l]]; // backtrack
    }
  }
}
// Вызов: permute([1,2,3], 0, 2);

Этот код генерирует все N! перестановок массива. Для N=3 выведет 6 вариантов.

Где применяется

На практике алгоритмы O(N!) используются только для очень маленьких N (обычно до 10-12). Для реальных задач применяют эвристики, приближённые алгоритмы или методы динамического программирования (например, алгоритм Хелда-Карпа для TSP с O(N²·2^N)).

Вывод: O(N!) — это крайне неэффективная сложность, характерная для задач полного перебора комбинаторных вариантов. Понимание таких алгоритмов помогает оценить границы применимости точных решений и необходимость использования оптимизаций.