This content has been automatically translated from Ukrainian.
Factorial complexity is a situation where the number of variants or combinations increases as a factorial of the number of elements. In other words, for n elements of possible permutations n!n!n! (n factorial), which quickly becomes a huge number even with small n.
This phenomenon is often found in combinatorics, planning, and full-sorting algorithms. For example, permutations of 5 elements – are 120 options, and for 10 elements there are already 3,628,800 of them.
Real-life examples:
- Permutation of tasks or routes <TAG1> planning delivery routes or tasks in the project.
- A game of chess or puzzles <TAG1> the number of possible move sequences grows extremely fast.
- Cryptography <TAG1> selection of combinations or passwords when completely searched.
Simple Ruby code to demonstrate factorial complexity:
def factorial(n)
(1..n).reduce(1, :*)
end
(1..10).each do |i|
puts "n=#{i} - #{factorial(i)} options"
end
Result:
n=1 - 1 variants n=2 - 2 variants n=3 - 6 variants n=4 - 24 variants n=5 - 120 variants n=6 - 720 variants n=7 - 5040 variants n=8 - 40320 variants n=9 - 362880 variants n=10 - 3628800 variants => 1..10
This example shows why factorial complexity quickly complicates the problem and makes direct selection of options practically impossible.
This post doesn't have any additions from the author yet.
