Ta treść została automatycznie przetłumaczona z ukraińskiego.
Funkcjonalna złożoność - to sytuacja, gdy liczba wariantów lub kombinacji rośnie jak silnia liczby elementów. Innymi słowy, dla n elementów możliwych permutacji n!n!n! (n silnia), co szybko staje się ogromną liczbą nawet przy małych n.
To zjawisko często występuje w kombinatoryce, planowaniu i algorytmach pełnego przeszukiwania. Na przykład, permutacje 5 elementów to 120 wariantów, a dla 10 elementów jest już 3 628 800.
Przykłady z życia codziennego:
- Permutacje zadań lub tras – planowanie tras dostaw lub zadań w projekcie.
- Gra w szachy lub łamigłówki – liczba możliwych sekwencji ruchów rośnie niezwykle szybko.
- Kryptografia – dobór kombinacji lub haseł przy pełnym przeszukiwaniu.
Prosty kod Ruby do demonstracji funkcjonalnej złożoności:
def factorial(n)
(1..n).reduce(1, :*)
end
(1..10).each do |i|
puts "n=#{i} - #{factorial(i)} wariantów"
end
Wynik:
n=1 - 1 wariantów n=2 - 2 wariantów n=3 - 6 wariantów n=4 - 24 wariantów n=5 - 120 wariantów n=6 - 720 wariantów n=7 - 5040 wariantów n=8 - 40320 wariantów n=9 - 362880 wariantów n=10 - 3628800 wariantów => 1..10
Ten przykład pokazuje, dlaczego funkcjonalna złożoność szybko komplikuje zadanie i czyni bezpośrednie przeszukiwanie wariantów praktycznie niemożliwym.
