[ALGORITHM] 09. O(n!)

O(n!)은 팩토리얼(Factorial) 시간 복잡도를 나타낸다.

이는 입력 크기 n에 대해 n의 팩토리얼에 비례하는 실행 시간을 가지는 알고리즘을 의미하며, 팩토리얼 시간 복잡도는

굉장히 높은 성능 비용을 가지기 때문에, 큰 입력에 대해서는 사용이 거의 불가능에 가깝다.

 

O(n!)의 알고리즘은 일반적으로 재귀적인 방법을 사용하여 문제를 작은 부분으로 나누고,

모든 가능성을 따져야 하는 경우에 나타나며 대표적인 예시로는 외판원 문제(Travelling Salesman Problem)가 있다.

 

아래는 재귀함수를 사용해 팩토리얼을 계산하는 코드이며, O(n!) 시간 복잡도를 가진다.

 

int factorial(int n) {

    if (n == 0 || n == 1) {
    
        return 1;
        
    } else {
    
        return n * factorial(n - 1);
    }
}