[ALGORITHM] 06. O(2ⁿ)

O(2ⁿ)은 입력 크기 n에 대해 2의 n 제곱에 비례하는 지수 시간 복잡도를 갖는 알고리즘을 나타낸다.

이는 입력 크기가 증가함에 따라 실행 시간이 기하급수적으로 증가하는 경우이며,

주로 재귀 알고리즘에서 이러한 시간 복잡도가 발생한다.

 

아래는 O(2ⁿ)의 시간 복잡도를 가지는 피보나치수열을 구하는 코드이다.

 

int fibonacci(int n) {

    if (n <= 1) {
    
        return n;
        
    } else {
    
        return fibonacci(n - 1) + fibonacci(n - 2); // 지수적으로 많은 계산이 필요함 : O(2ⁿ)
    }
}