GM 오락실
← 개인 공부 · Algorithm
STUDY NOTE · 개념 정리

시간 복잡도와 빅오 정리: 점근 표기법, 대표 복잡도, 자료구조별 연산 비용

Algorithm
시간 복잡도는 입력 크기 n이 커질 때 연산 횟수가 얼마나 빨리 늘어나는지를 나타낸다. 빅오(O)는 그 증가율의 상한을 표기하며, 상수와 낮은 차수 항은 버리고 가장 빠르게 커지는 항만 남긴다. 실무에서는 보통 최악의 경우를 빅오로 말한다.

1. 왜 실행 시간이 아니라 연산 횟수인가

같은 코드도 CPU, 언어, 입력 데이터에 따라 실행 시간이 다르다. 그래서 알고리즘 자체의 효율은 기계와 무관하게 입력이 커질 때 연산 횟수가 늘어나는 모양으로 비교한다. n이 10일 때는 O(n²)도 빠르지만, n이 100만이 되면 O(n)과 O(n²)의 차이는 수십만 배가 된다.

2. 점근 표기법

표기의미비유
O (빅오)상한: 이보다 빨리 늘어나지 않는다아무리 오래 걸려도 이 정도
Ω (빅오메가)하한: 이보다 느리게 늘어나지 않는다아무리 빨라도 이 정도
Θ (빅세타)상한과 하한이 같다 (정확한 증가율)딱 이 정도

최선·평균·최악은 어떤 입력이냐의 구분이고, O·Ω·Θ는 증가율을 어떻게 표기하느냐의 구분이다. 예를 들어 퀵 정렬은 평균 Θ(n log n), 최악 Θ(n²)다. 면접에서 "빅오는 최악의 경우"라고 말하는 건 흔한 단순화이고, 정확히는 상한 표기다.

3. 계산 규칙

규칙예결과
상수 계수는 버린다3n + 5O(n)
낮은 차수 항은 버린다n² + 100nO(n²)
순차 실행은 더한다O(n) 반복문 뒤에 O(n²) 반복문O(n²)
중첩 실행은 곱한다n번 도는 반복문 안에 n번 도는 반복문O(n²)
입력이 둘이면 둘 다 남긴다길이 n 배열과 길이 m 배열을 각각 순회O(n + m)
// O(n): 한 번 훑기
for (int i = 0; i < n; i++) sum += arr[i];

// O(n²): 모든 쌍 비교
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == arr[j]) return true;

// O(log n): 매번 절반으로 줄이기
while (n > 1) n /= 2;

두 번째 반복문은 비교 횟수가 n(n-1)/2라서 정확히는 n²/2 정도지만, 상수 1/2을 버려 O(n²)이다.

4. 대표 복잡도

복잡도이름예1초 안에 다룰 수 있는 n (대략)
O(1)상수배열 인덱스 접근, 해시 조회(평균)제한 없음
O(log n)로그이진 탐색, 균형 트리 탐색사실상 제한 없음
O(n)선형배열 순회, 최댓값 찾기약 1억
O(n log n)선형 로그병합 정렬, 힙 정렬, 효율적인 정렬 전반약 수백만
O(n²)이차이중 반복문, 버블·삽입 정렬약 1만
O(n³)삼차삼중 반복문, 플로이드-워셜약 500
O(2ⁿ)지수부분집합 전부 확인약 25
O(n!)팩토리얼순열 전부 확인약 10

마지막 열은 "단순 연산을 1초에 1억 번 정도 한다"고 가정한 경험칙이다. 코딩 테스트에서 입력 크기를 보고 허용되는 복잡도를 거꾸로 추정할 때 쓴다. n이 10만이면 O(n²)은 100억 번이라 불가능하고, O(n log n) 이하가 필요하다.

5. 로그는 왜 나오나

문제 크기를 매번 절반(또는 일정 비율)으로 줄이면 log n번 만에 1이 된다. n = 1,000,000이어도 log₂n은 약 20이다. 이진 탐색, 균형 이진 트리, B+Tree 인덱스가 빠른 이유다.

int binarySearch(int[] sorted, int target) {
int lo = 0, hi = sorted.length - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1; // 오버플로 방지
if (sorted[mid] == target) return mid;
if (sorted[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}

6. 자료구조별 연산 비용

자료구조인덱스 접근탐색삽입/삭제비고
배열 (동적 배열)O(1)O(n)끝: O(1) 분할 상환, 중간: O(n)중간 삽입은 뒤 원소를 밀어야 함
연결 리스트O(n)O(n)위치를 알면 O(1)위치를 찾는 데 O(n)
해시 테이블-평균 O(1), 최악 O(n)평균 O(1)충돌이 몰리면 느려짐
균형 이진 탐색 트리-O(log n)O(log n)정렬 순서 유지
이진 힙-O(n)삽입·최솟값 삭제 O(log n)최솟값 조회는 O(1)

7. 분할 상환(Amortized) 분석

동적 배열(자바 ArrayList)은 용량이 차면 더 큰 배열을 만들어 전부 복사한다. 이 순간은 O(n)이지만 자주 일어나지 않는다. 용량을 일정 비율로 늘리면(자바 ArrayList는 약 1.5배) n번 추가하는 동안 복사 비용의 합이 O(n)이므로, 한 번 추가의 평균 비용은 O(1)로 본다. 이것을 분할 상환 O(1)이라고 한다.

8. 공간 복잡도

알고리즘이 추가로 쓰는 메모리도 같은 방식으로 표기한다. 입력 배열 외에 크기 n짜리 보조 배열을 만들면 O(n), 변수 몇 개만 쓰면 O(1)이다. 재귀는 호출 깊이만큼 스택을 쓴다는 점을 놓치기 쉽다. 깊이 n까지 들어가는 재귀는 공간 O(n)이고, 너무 깊으면 StackOverflowError가 난다.

9. 실제로 어떻게 적용되나

  1. 중복 검사: 이중 반복문으로 모든 쌍을 비교하면 O(n²)이다. HashSet에 넣으면서 이미 있는지 확인하면 O(n)이 된다. 메모리를 조금 더 쓰고 시간을 크게 줄이는 전형적인 교환이다.
  2. 반복문 안의 contains: List.contains는 O(n)이라 n번 반복 안에서 호출하면 O(n²)이다. 조회 대상을 미리 Set이나 Map으로 바꿔 두면 O(n)이 된다.
  3. 반복문 안의 쿼리: 주문 목록 n건을 돌면서 건마다 상품을 조회하면 쿼리가 n번 나간다. 복잡도 자체는 O(n)이어도 한 번에 드는 상수(네트워크 왕복)가 크다. IN 절이나 조인으로 한 번에 가져온다.
  4. DB 인덱스: 인덱스가 없으면 테이블 전체를 훑는 O(n), B+Tree 인덱스를 타면 O(log n)으로 찾는다.

10. 면접 질문으로 정리

  1. Q. 시간 복잡도란? 입력 크기가 커질 때 알고리즘의 연산 횟수가 증가하는 정도를 나타낸 것이다. 실행 환경과 무관하게 알고리즘의 효율을 비교하려고 쓴다.
  2. Q. 빅오에서 상수를 버리는 이유는? n이 충분히 커지면 증가율이 가장 큰 항이 전체를 지배하기 때문이다. 다만 실제 성능에서는 상수도 중요할 수 있다.
  3. Q. O(n log n)과 O(n²)의 차이를 체감할 수 있게 설명하면? n이 100만일 때 n log n은 약 2천만, n²은 1조다. 앞의 것은 1초 안에 끝나지만 뒤의 것은 몇 시간이 걸릴 수 있다.
  4. Q. ArrayList의 add가 O(1)인 이유는? 가끔 일어나는 배열 확장(O(n))을 여러 번의 추가에 나눠 보면 평균이 상수가 되기 때문이다. 이를 분할 상환 O(1)이라고 한다.
  5. Q. 해시 테이블 조회는 항상 O(1)인가? 평균 O(1)이다. 해시 충돌이 한 버킷에 몰리면 최악 O(n)까지 느려질 수 있다.
Gunmo Lee
since 2021.07
시간 복잡도와 빅오 정리: 점근 표기법, 대표 복잡도, 자료구조별 연산 비용 | GM 오락실