Loading...

O(2^n) - 지수 시간

보통

O(2^n) - Exponential Time

부분집합으로 배우는 O(2^n). 매 선택마다 2배씩 폭발하는 경우의 수!

📊 복잡도

구분	복잡도
최선	O(2^n)
평균	O(2^n)
최악	O(2^n)
공간	O(n)

🏷️ 태그

복잡도지수부분집합

📖 개념 소개

O(2^n)은 각 원소마다 2가지 선택이 있어 경우의 수가 2^n개가 됩니다. N이 1 증가할 때마다 시간이 2배!

1/11

Loading...

📦부분집합이란?

{A, B, C}의 모든 부분집합을 구해봅시다. 부분집합: 원래 집합에서 일부(또는 전체/없음)를 선택한 것 총 몇 개일까요?

기초 학습

O(2^n) - 지수 시간

정의

O(2^n)은 각 원소마다 2가지 선택이 있어 경우의 수가 2^n개가 됩니다. N이 1 증가할 때마다 시간이 2배!

핵심 특성

✓매 선택마다 2배
✓N+1 → 시간 2배
✓N>30이면 감당 불가

시간 복잡도

최선

O(2^n)

평균

O(2^n)

최악

O(2^n)

공간 복잡도

O(n)

O(2^n) - 지수 시간 | AlgoNote