빅오 표기법 (Big O Notation)
알고리즘의 효율을 측정하는 가장 직관적인 방법은 실제로 실행해보고 시간을 재는 것이다. 하지만 이 방법은 서버 사양, 데이터 크기, 실행 환경에 따라 결과가 달라지기 때문에 알고리즘 자체의 효율이라고 보기 어렵다.
빅오 표기법은 이 문제를 해결하기 위해 입력 크기 N에 따라 연산 횟수가 어떻게 증가하는지를 표현한다. 환경과 무관하게 알고리즘 자체의 성장 패턴을 비교할 수 있다.
상수 계수는 표기에서 제거한다. O(n/2)와 O(n)은 같은 표기다. N이 무한대로 커질수록 앞의 계수는 증가 패턴에 영향을 주지 않기 때문이다. 같은 이유로 낮은 차수 항도 제거한다. O(n² + n)은 O(n²)으로 표기한다.
자주 사용하는 복잡도를 빠른 순서로 나열하면 다음과 같다.
| 복잡도 | 대표 예시 |
|---|---|
| O(1) | 배열 인덱스 접근 |
| O(log n) | 이진 탐색 |
| O(n) | 선형 탐색 |
| O(n log n) | 병합 정렬, 퀵 정렬 평균 |
| O(n²) | 버블 정렬, 이중 for문 |
| O(2^n) | 피보나치 재귀, 부분집합 탐색 |
시간 복잡도와 공간 복잡도
빅오 표기법은 두 가지 기준에 적용된다.
시간 복잡도는 입력 크기 N에 따라 연산 횟수가 얼마나 늘어나는지를 나타낸다.
공간 복잡도는 알고리즘 실행 중 추가로 사용하는 메모리가 N에 따라 얼마나 늘어나는지를 나타낸다. 입력 데이터 자체는 제외하고, 알고리즘이 실행되면서 새로 할당하는 메모리만 센다.
아래 두 코드는 시간 복잡도는 같지만 공간 복잡도가 다르다.
// 공간 복잡도 O(n) — 입력 크기만큼 새 배열 할당
int[] copy = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
copy[i] = arr[i];
}
// 공간 복잡도 O(1) — N이 커져도 추가 변수는 하나뿐
int sum = 0;
for (int x : arr) {
sum += x;
}공간 복잡도가 실질적으로 중요해지는 경우는 재귀 함수다. 재귀는 호출마다 현재 함수의 상태(파라미터, 복귀 주소 등)가 콜 스택에 쌓인다. N번 호출하면 스택도 N개 쌓이므로 공간 복잡도는 O(n)이 된다.
// 공간 복잡도 O(n) — 호출 깊이만큼 스택 쌓임
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// 공간 복잡도 O(1) — 변수 3개만 사용, 스택 쌓이지 않음
int fib(int n) {
int a = 0, b = 1;
for (int i = 0; i < n; i++) {
int tmp = a + b; a = b; b = tmp;
}
return a;
}N이 충분히 크면 재귀 방식은 StackOverflowError가 발생할 수 있다. 메모리 제한이 있는 환경에서는 시간 복잡도뿐 아니라 공간 복잡도도 함께 고려해야 한다.
Best / Average / Worst Case
같은 알고리즘이라도 입력 상태에 따라 실제 연산 횟수는 달라진다. 이를 세 가지 케이스로 구분한다.
ArrayList, LinkedList, HashSet에서 특정 값을 탐색하는 경우를 비교하면 다음과 같다.
ArrayList는 내부적으로 연속된 배열 구조다. 인덱스를 알면 O(1)이지만, 값으로 탐색하면 처음부터 순서대로 확인한다.
- Best: 첫 번째 원소가 정답 → O(1)
- Worst: 마지막 원소가 정답 → O(n)
LinkedList는 Java에서 양방향(doubly linked list)으로 구현된다. head와 tail 양쪽에서 탐색할 수 있어 처음과 끝은 바로 접근 가능하지만, 중간 원소는 어느 쪽에서 탐색해도 절반을 순회해야 한다.
- Best: 첫 번째 또는 마지막 원소 → O(1)
- Worst: 정중앙 원소 → O(n)
HashSet은 해시 함수를 통해 버킷을 찾아 바로 접근한다. 해시 충돌이 없으면 O(1)이지만, 충돌이 누적되면 같은 버킷 안에서 선형 탐색이 발생한다.
- Best / Average: O(1)
- Worst: 모든 원소가 같은 버킷에 몰린 경우 → O(n)
분할 상환 분석 (Amortized Analysis)
ArrayList에 원소를 추가할 때, 배열이 꽉 차면 내부적으로 더 큰 배열을 새로 만들고 기존 원소를 전부 복사한다. 이 순간의 비용은 O(n)이다.
그렇다면 ArrayList의 add는 O(n)일까?
n번 add를 반복하면 확장은 드물게 발생하고 나머지는 O(1)이다. 전체 비용을 연산 횟수로 나누면 평균 O(1)이 나온다. 이처럼 연속된 연산의 총 비용을 연산 횟수로 나눠 평균을 구하는 방식을 분할 상환 분석이라고 한다.
Average case와 헷갈릴 수 있는데 둘은 다르다. Average case는 입력이 랜덤하게 분포한다는 가정 아래 평균 비용을 구한다. 반면 분할 상환 분석은 입력 분포를 가정하지 않고, 연산을 n번 수행했을 때 총 비용이 얼마인지를 기준으로 수학적으로 보장된 평균을 구한다.
ArrayList add는 입력이 무엇이든 상관없이 분할 상환 O(1)이 보장된다.
