빅오 표기법은 입력 크기가 커질 때 알고리즘의 실행 시간이 어떤 속도로 증가하는지 표현하는 방법이다. 정확히 몇 밀리초가 걸리는지를 말하기보다, 데이터가 10개에서 1만 개, 100만 개로 늘어날 때 시간이 어떤 형태로 커지는지를 보는 데 가깝다.
그래서 빅오에서는 작은 상수나 낮은 차수의 항을 과감하게 버린다. O(2n)은 결국 O(n)으로 보고, O(n^2 + n)은 O(n^2)로 본다. 입력이 충분히 커지면 가장 빠르게 증가하는 항이 전체 성능을 지배하기 때문이다.
자주 보는 복잡도
자주 보는 복잡도는 대략 이런 순서로 커진다.
O(1): 입력 크기와 상관없이 거의 일정하다. 배열 인덱스 접근이나 해시 조회가 대표적이다.O(log n): 입력을 매번 절반씩 줄인다. 이진 탐색이 여기에 해당한다.O(n): 입력 전체를 한 번 훑는다. 선형 탐색이 대표적이다.O(n log n): 정렬 알고리즘에서 자주 나온다. 병합 정렬, 힙 정렬 등이 여기에 가깝다.O(n^2): 중첩 반복문처럼 모든 쌍을 비교할 때 자주 나온다.O(2^n): 선택지가 매 단계마다 두 배로 늘어나는 경우다. 단순 재귀 피보나치나 모든 부분집합 탐색에서 볼 수 있다.
반복문으로 계산하기
코드를 볼 때는 먼저 반복문을 본다. 배열을 한 번 순회하면 보통 O(n)이다.
public int findElement(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}위 코드는 운이 좋으면 첫 번째에서 끝날 수도 있지만, 빅오에서는 보통 최악의 경우를 기준으로 본다. 찾는 값이 없거나 마지막에 있다면 배열 전체를 확인해야 하므로 O(n)이다.
이진 탐색은 조금 다르다. 정렬된 배열에서 중간 값을 보고, 찾는 값이 왼쪽에 있는지 오른쪽에 있는지 판단한 뒤 나머지 절반을 버린다.
public int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] < key) {
low = mid + 1;
} else if (arr[mid] > key) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}탐색 범위가 반복할 때마다 절반으로 줄어들기 때문에 O(log n)이다. 입력이 1,000개에서 1,000,000개로 커져도 확인 횟수는 선형으로 늘지 않는다.
중첩 반복문은 보통 더 조심해서 봐야 한다. 아래 버블 정렬은 바깥 반복문과 안쪽 반복문이 함께 돌면서 인접한 값을 계속 비교한다.
public void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}대략 n번 안에서 다시 n번 가까이 비교하므로 O(n^2)로 본다. 실제 비교 횟수는 n * (n - 1) / 2에 가깝지만, 빅오에서는 가장 큰 성장 형태만 남긴다.
빅오만으로는 부족하다
다만 빅오만으로 알고리즘의 실제 성능을 모두 설명할 수는 없다. 입력 크기가 작으면 상수 시간이 더 중요할 수 있고, 캐시 효율이나 메모리 사용량이 결과를 크게 바꾸기도 한다. 같은 O(n)이어도 구현 방식에 따라 체감 성능은 달라진다.
그래도 빅오는 알고리즘을 처음 비교할 때 좋은 기준점이 된다. 코드를 볼 때 “입력이 커질수록 몇 번 반복하는가”, “매번 문제 크기가 얼마나 줄어드는가”, “중첩된 작업이 있는가”를 먼저 확인하면 대부분의 기본 복잡도는 계산할 수 있다.