Факторіальна складність - це ситуація, коли кількість варіантів або комбінацій зростає як факторіал числа елементів. Іншими словами, для n елементів можливих перестановок n!n!n! (n факторіал), що швидко стає величезним числом навіть при невеликих n.
Таке явище часто зустрічається в комбінаториці, плануванні та алгоритмах повного перебору. Наприклад, перестановки 5 елементів – це 120 варіантів, а для 10 елементів їх уже 3 628 800.
Приклади з реального життя:
- Перестановки задач або маршрутів – планування маршрутів доставки чи завдань у проєкті.
- Гра у шахи або головоломки – кількість можливих послідовностей ходів зростає надзвичайно швидко.
- Криптографія – підбір комбінацій або паролів при повному переборі.
Простий Ruby-код для демонстрації факторіальної складності:
def factorial(n)
(1..n).reduce(1, :*)
end
(1..10).each do |i|
puts "n=#{i} - #{factorial(i)} варіантів"
end
Результат:
n=1 - 1 варіантів n=2 - 2 варіантів n=3 - 6 варіантів n=4 - 24 варіантів n=5 - 120 варіантів n=6 - 720 варіантів n=7 - 5040 варіантів n=8 - 40320 варіантів n=9 - 362880 варіантів n=10 - 3628800 варіантів => 1..10
Цей приклад показує, чому факторіальна складність швидко ускладнює задачу і робить прямий перебір варіантів практично неможливим.
Цей допис поки що не має жодних доповнень від автора/ки.
