알고리즘에서 꼭 나오는 시간복잡도 정리

1. 시간복잡도란?

시간복잡도(Time Complexity)란
입력 크기 N이 커질 때 알고리즘이 얼마나 빠르게 실행되는지를 나타내는 척도이다.
즉, 알고리즘이 문제를 얼마나 효율적으로 해결하는지를 수치로 표현한 개념이다.

입력값이 커질수록 성능 차이가 두드러지기 때문에, 코딩 테스트에서는 반드시 고려해야 한다.

---

2. 시간복잡도 표 정리

아래는 알고리즘에서 자주 등장하는 시간복잡도와 그에 따른 수행 가능한 최대 입력 크기(N)의 예시이다.

시간복잡도입력 크기 N의 최대 범위설명

O(1)	제한 없음	상수 시간, 입력과 무관하게 항상 같은 시간
O(logN)	1억 이상 가능	이진 탐색 등 (입력을 절반씩 줄이는 방식)
O(N)	1억 이하	단순 반복, 배열 전체 탐색 등
O(NlogN)	100만 ~ 200만 이하	병합정렬, 힙정렬 등
O(N²)	10,000 이하	이중 for문 등 (브루트포스 탐색)
O(N³)	500 이하	3중 for문, 완전 탐색 등
O(2ⁿ)	20 이하	부분집합, 백트래킹 (조합의 모든 경우 탐색)
O(N!)	10 이하	순열 완전탐색, 외판원 문제 등

---

3. 빅오(Big-O) 표기법

시간복잡도는 보통 Big-O 표기법을 사용한다.
이는 최악의 경우 시간을 기준으로 알고리즘의 성능을 분석할 때 사용한다.

• O(1): 입력 크기와 관계없이 항상 같은 시간
• O(N): 입력 크기에 비례
• O(N²): 입력이 두 배가 되면 처리 시간은 네 배
• O(logN): 이진 탐색처럼 매번 절반씩 줄어드는 구조
• O(NlogN): 정렬 알고리즘에서 자주 등장

---

4. 입력 크기에 따른 선택 기준

N 크기사용 가능한 시간복잡도

N ≤ 10	O(N!), O(2ⁿ) 가능
N ≤ 100	O(N³) 가능
N ≤ 1,000	O(N²) 가능
N ≤ 100,000	O(NlogN), O(N) 가능
N ≤ 10⁷ ~ 10⁸	O(N), O(logN), O(1)만 가능

 

→ 대부분의 코딩테스트 환경에서는 1초에 약 1억 번 연산이 가능하다고 가정한다.

 

---

5. 시간복잡도 계산 팁

• 입력 크기 N을 기준으로 for문 깊이를 생각한다
  • O(N): 단일 for문
  • O(N²): 이중 for문
  • O(N³): 삼중 for문
• 정렬이 들어가면 보통 O(NlogN)
• 재귀 호출은 트리처럼 퍼질 수 있어 반드시 시간복잡도 체크
• 문제를 읽을 때 주어진 N의 크기를 먼저 파악한 뒤, 접근 전략을 선택하는 것이 중요하다

---

6. 마무리

시간복잡도는 코딩 테스트에서 가장 중요한 기준 중 하나다.
알고리즘의 성능이 좋지 않으면 입력이 커졌을 때 시간 초과가 발생하므로,
문제를 풀기 전 입력 크기 → 시간복잡도 허용 범위 → 알고리즘 선택의 흐름을 익히는 것이 중요하다.

앞으로 각 문제를 풀 때마다 코드와 함께 시간복잡도도 반드시 분석해보려 한다.
이 정리는 블로그 시리즈로 계속 업데이트할 계획이다.