1. 시간복잡도
시간복잡도(Time Complexity)란?
시간복잡도란 입력 크기(N)가 커질수록 프로그램이 얼마나 느려지는지를 표현하는 개념이다.
여기서 중요한 점은
👉 “몇 초 걸리느냐”가 아니라
👉 “입력이 커질수록 얼마나 빨리 느려지느냐” 이다.
왜 시간복잡도가 필요한가?
- 같은 문제를 푸는 코드라도 다음처럼 차이가 날 수 있다.
코드 A: 데이터가 2배가 되면 시간도 2배
코드 B: 데이터가 2배가 되면 시간은 4배, 8배로 폭증 - 시간복잡도는 이런 성능 차이를 비교하기 위한 기준이다.
ex. 시간제한 2초 -> 2억 연산 안에 답이 나와야 함
Big-O 표기법 (O 표기법)
- 시간복잡도는 보통 Big-O로 표현한다. 최악일 때의 연산횟수를 나타낸 표기법.
O(1), O(N), O(N²), O(N log N) ...- 정확한 횟수는 중요하지 않고, 증가 추세만 본다
그래서 상수는 무시한다.
O(2N) → O(N)
O(100N) → O(N)log N 이란 무엇인가?
-
log N의 의미
“어떤 값을 반으로 줄여서 1이 될 때까지의 횟수” -
예시
N = 8
8 → 4 → 2 → 1반으로 줄인 횟수: 3번
따라서 log₂ 8 = 3 (알고리즘에서는 거의 항상 log N = log₂ N 로 취급)
- log는 값이 아니라 “몇 번 반복했는지”를 의미한다
ex. log₂ 100 은?
log₂ 128 = 7
log₂ 100 ≈ 6.646.64지만, 연산 횟수는 정수이므로 7번
log N이 등장하는 코드 형태
while (n > 1) {
n = n / 2;
}- 이 코드는:
n이 절반씩 줄어듦
반복 횟수는 log N
시간복잡도는 O(log N)
log N의 특징
입력이 커져도 증가 속도가 매우 느리다
N이 1,000,000이 되어도 log N은 약 20 정도
그래서 log N은 단독으로는 굉장히 빠른 시간복잡도다.
주요 시간복잡도 종류
1️⃣ O(1) — 상수 시간
입력 크기와 무관하게 항상 같은 시간
int x = arr[0]; // 인덱스로 바로 접근✔️ 가장 빠름
2️⃣ O(N) — 선형 시간
입력 크기만큼 한 번씩만 처리
for (int i = 0; i < N; i++) {
System.out.println(arr[i]);
}✔️ N이 2배 → 실행 시간도 2배
3️⃣ O(2N) — 사실상 O(N)
for (int i = 0; i < N; i++) { } // 1
for (int i = 0; i < N; i++) { } // 2✔️ N + N = 2N
✔️ 상수는 무시 → O(N)
4️⃣ O(N²) — 이중 반복문
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
...
}
}✔️ N × N = N²
✔️ 입력이 조금만 커져도 성능 급격히 악화
✔️ 대규모 데이터에서 매우 위험
5️⃣ O(N log N)
for (int i = 0; i < N; i++) {
binarySearch(arr); // log N
}✔️ N번 반복 × 반으로 줄이는 작업
✔️ 연산량 = N × log N
👉 log N은 작아 보여도
👉 N과 곱해지면 커질 수 있다
시간복잡도 판단 팁
✅ 비교적 안전한 구조
단일 반복문
투포인터
슬라이딩 윈도우
❌ 위험 신호
중첩 반복문
모든 경우의 수 탐색
같은 계산을 반복하는 구조
요약
시간복잡도는 입력이 커질수록 실행 시간이 어떻게 증가하는지를 나타낸다.
log N은 값을 반으로 줄이는 과정을 몇 번 반복했는지를 의미한다.
O(2N)은 O(N)과 같다.
O(N²)는 입력이 커지면 급격히 느려진다.
좋은 알고리즘은 같은 일을 반복하지 않는다.문제 요구 타입 분류 (이게 제일 중요 ⭐)
| 문제 문장에 자주 나오는 말 | 떠올릴 것 |
|---|---|
| 두 수의 합 / 차 | 투 포인터 / 해시 |
| 구간 합 | 누적합 |
| 정렬 후 | 정렬 + 탐색 |
| 최댓값 / 최솟값 | 그리디 |
| K번째 | 힙 / 정렬 |
| 범위 쿼리 | 세그트리 / 누적합 |
| 존재 여부 | Set / Map |
시간복잡도 그래프
연산횟수 계산 방법
연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기
알고리즘 적합성 평가
ex. N = 1,000,000 일때, 2초 시간제한
1) 버블 정렬(N²) = 1,000,000,000,000 > 200,000,000 -> ❌부적합
2) 병합 정렬(N log N)
= 1,000,000 log(1,000,000)
= 1,000,000 × log₂(1,000,000)
≈ 1,000,000 × 약 20
≈ 약 20,000,000 < 200,000,000 -> 🅾️적합
