Проверяет понимание факториальной сложности алгоритмов и её практического значения.
O(N!) — это обозначение факториальной временной сложности в нотации Big O. Оно описывает алгоритмы, время выполнения которых растёт пропорционально факториалу от размера входных данных N. Факториал N! — это произведение всех натуральных чисел от 1 до N: N! = 1 * 2 * 3 * ... * N.
Такая сложность типична для алгоритмов, которые перебирают все возможные перестановки элементов. Классический пример — решение задачи коммивояжёра методом полного перебора, где нужно найти кратчайший маршрут через N городов, посетив каждый ровно один раз.
function generatePermutations(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 perms = generatePermutations(remaining);
for (let perm of perms) {
result.push([current].concat(perm));
}
}
return result;
}
// Для массива из N элементов будет N! перестановок
console.log(generatePermutations([1,2,3]).length); // 6 = 3!Вывод: алгоритмы с факториальной сложностью следует избегать в реальных проектах. Если задача требует перебора перестановок, необходимо искать приближённые решения или использовать эвристики.
