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

Проблема

Задачи вроде «найти оптимальный порядок обхода городов» или «расставить n предметов наилучшим образом» звучат так, будто единственный надёжный способ решить их - проверить все возможные порядки и выбрать лучший. Код для этого пишется буквально в одну рекурсивную функцию, выглядит корректно и проходит любые тесты на 4-5 элементах. Опасность в том, что рост числа перестановок скрыт за восклицательным знаком в формуле, и никакой интуиции «n чуть больше - работы чуть больше» здесь не работает: перестановок 10 элементов уже 3 628 800, а 15 элементов - больше триллиона.

Решение

Операция попадает в O(n!), если решение перебирает все возможные упорядочивания n элементов, и на каждом шаге число оставшихся вариантов уменьшается ровно на единицу. Узнать такой код можно по форме: рекурсия с циклом внутри, где на каждом уровне выбор идёт из оставшихся элементов, а не из фиксированного набора вариантов. Классический пример - генерация всех перестановок массива через обмен элементов местами: на первом уровне рекурсии n вариантов выбора, на втором - n - 1, и так далее до единственного оставшегося элемента.

Как это работает

Формально n! ("n факториал") - это произведение всех целых чисел от 1 до n: n! = n · (n - 1) · (n - 2) · ... · 2 · 1. Для permute это ровно число всех перестановок массива из n различных элементов: на первую позицию можно поставить любой из n элементов, на вторую - любой из оставшихся n - 1, и так далее, пока не останется один-единственный вариант для последней позиции.

Числа делают рост наглядным. 5! = 120 - терпимо. 10! = 3 628 800 - уже больше трёх с половиной миллионов. 15! ≈ 1.3 триллиона. 20! ≈ 2.4 квинтиллиона - число, которое современный процессор не переберёт даже за годы непрерывной работы, даже если каждая перестановка проверяется за одну наносекунду.

Сравнение с O(2ⁿ) показывает, почему факториал считается ещё более катастрофическим классом. У экспоненты множитель на каждом шаге один и тот же - постоянная c. У факториала множитель сам уменьшается с каждым уровнем рекурсии, но остаётся числом, сравнимым с n, а не с постоянной двойкой - поэтому n! обгоняет 2ⁿ уже к n ≈ 4-5 и дальше отрывается ускоряющимися темпами: на n = 20 разрыв - больше двух триллионов раз (2 432 902 008 176 640 000 против 1 048 576).

Разница между «перебрать все подмножества» (O(2ⁿ)) и «перебрать все порядки» (O(n!)) - это разница между вопросом «что входит в набор» и вопросом «в каком порядке». Подмножеств множества из n элементов - 2ⁿ. Упорядочиваний того же множества - n!, потому что для каждого подмножества-набора нужно ещё перебрать все способы его расставить. Это и объясняет, почему факториальный рост всегда обгоняет экспоненциальный на одном и том же n.

Практически ни одна промышленная система не оставляет задачу с O(n!) как есть. Задача коммивояжёра сводится к O(n² · 2ⁿ) алгоритмом Хелда-Карпа через динамическое программирование по подмножествам, или решается приближённо эвристиками (ближайший сосед, генетические алгоритмы), которые не гарантируют оптимум, но дают хорошее решение за полиномиальное время. Факториальный перебор в реальном коде почти всегда сигнал: задача сформулирована шире, чем нужно, и стоит поискать более узкую переформулировку.

Небольшая, но реальная оптимизация внутри самого класса O(n!) - отсечение симметричных перестановок: если часть элементов одинакова, многие перестановки совпадают друг с другом, и их можно не генерировать повторно. Это не меняет Big O в общем случае (при всех различных элементах симметрии нет), но заметно снижает реальную работу на входах с повторами.

Нюансы выбора

Гарантированно крошечное n - если условие задачи фиксирует n на уровне 8-10 и меньше, полный перебор перестановок проще писать и проверять, чем искать более узкую формулировку.

Против O(2ⁿ) - если задача сводится к выбору набора элементов, а не их порядка, перебор подмножеств (O(2ⁿ)) почти всегда достаточен и заметно дешевле полного перебора перестановок.

Против динамического программирования по маскам - как только задача о порядке допускает переформулировку через подмножества посещённых элементов (как в задаче коммивояжёра), O(n!) сводится к O(n² · 2ⁿ) - всё ещё катастрофически, но на порядки практичнее.

Против эвристик - когда точный оптимум не обязателен, приближённые методы (ближайший сосед, локальный поиск, генетические алгоритмы) дают решение, близкое к лучшему, за полиномиальное время вместо факториального.

Примеры в коде

Прямое решение задачи коммивояжёра - справочная точка отсчёта в любом курсе по алгоритмам: наглядно показывает, зачем вообще нужны Хелд-Карп, эвристики и приближённые методы.

Планирование расписаний (составление порядка выполнения n задач на одном ресурсе) в наивной формулировке сводится к перебору n! порядков; на практике решается жадными эвристиками или целочисленным программированием.

Задача о восьми ферзях и её обобщение на n ферзей - классический пример из теории алгоритмов, где наивный перебор расстановок факториален, а бэктрекинг с отсечением атакующих позиций резко сокращает реальное время работы.

Выравнивание последовательностей ДНК/белков при сравнении более двух последовательностей одновременно - наивный многосторонний перебор порядков выравнивания растёт факториально с числом последовательностей, поэтому используются приближённые прогрессивные методы (как в ClustalW).

Когда применять

• Когда n гарантированно совсем маленькое (до 8-10) и задача действительно требует именно порядка элементов, а не просто их набора.
• Для эталонной проверки более быстрого алгоритма на маленьких данных - полный перебор перестановок даёт заведомо правильный ответ, с которым можно сверить оптимизированное решение.

Примеры из практики

• Прямой перебор задачи коммивояжёра - учебная точка отсчёта: проверить все n! возможных маршрутов и выбрать самый короткий, работает лишь при считаных городах.
• Генерация всех расстановок ферзей на шахматной доске без учёта атак - перебор всех n! расположений n ферзей на n позициях по одной в столбце.