정의
O(2^n)은 각 원소마다 2가지 선택이 있어 경우의 수가 2^n개가 됩니다. N이 1 증가할 때마다 시간이 2배!
핵심 특성
- ✓매 선택마다 2배
- ✓N+1 → 시간 2배
- ✓N>30이면 감당 불가
활용 사례
이런 상황에서 사용됩니다:
📦
부분집합 생성
N개 원소 → 2^N개
🐇
피보나치 재귀
중복 계산의 악몽
🧩
백트래킹
모든 경우 탐색
복잡도
시간 복잡도
최선
O(2^n)
평균
O(2^n)
최악
O(2^n)
공간 복잡도
O(n)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기