빅오 표기법과 복잡도 계산법

빅오 표기법은 알고리즘의 성능을 나타내는 표기법이다. 알고리즘이 처리하는 데이터의 크기가 커질수록 시간이 어떻게 증가하는지를 나타낸다. 일반적으로 최악의 경우를 기준으로 하며, 알고리즘이 얼마나 빨리 작동할지를 예측하는 데 사용된다. 상수나 작은 변화는 무시하고 가장 영향력이 큰 성장을 나타내는 함수로 표현한다.

주요 빅오 표기법 종류

O(1) - 상수 시간 복잡도: 입력 크기와 상관없이 항상 일정한 시간이 소요된다. (예: 배열의 특정 인덱스 접근, 해시 테이블 값 조회)
O(log n) - 로그 시간 복잡도: 입력 크기가 커질수록 처리 시간이 로그적으로 증가한다. (예: 이진 탐색, 균형 이진 트리)
O(n) - 선형 시간 복잡도: 입력 크기에 비례해서 시간이 증가한다. (예: 배열의 모든 요소 순회)
O(n log n) - 선형 로그 시간 복잡도: n번의 로그 연산을 반복하는 경우다. (예: 퀵정렬, 병합정렬)
O(n^2) - 이차 시간 복잡도: 입력 크기의 제곱에 비례해 시간이 증가한다. (예: 버블정렬)
O(2^n) - 지수 시간 복잡도: 입력 크기가 1씩 증가할 때마다 시간이 두 배로 늘어난다. (예: 피보나치 재귀, 모든 부분집합 찾기)

빅오 표기법 계산 방법

상수 값 제거: 빅오 표기법에서는 상수를 무시한다. O(2n)이나 O(3n)은 O(n)으로 축약된다.
가장 빠르게 증가하는 항만 유지: 여러 항이 있을 경우 가장 큰 성장을 나타내는 항만 남긴다. O(n^2 + n)은 O(n^2)로 단순화된다.
루프 분석: 루프 안의 연산을 분석한다.
- 단일 루프: O(n)
- 중첩된 이중 루프: O(n^2)
- 삼중 루프: O(n^3)
재귀적 호출 분석: 재귀 알고리즘의 복잡도는 재귀 함수가 호출되는 횟수에 따라 계산한다.
- 피보나치 수열 같은 재귀 호출은 O(2^n)처럼 지수적으로 증가할 수 있다.
- 분할 정복 알고리즘(예: 병합 정렬)은 O(n log n)으로 분석된다.

빅오 계산 예시

선형 탐색 예시

public int findElement(int[] arr, int key) {
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] == key) {
			return i;
		}
	}
}

배열을 순차적으로 탐색하므로 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)이다.

버블 정렬 예시

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;
			}
		}
	}
}

배열을 두 번 반복하면서 비교하고 정렬하므로 O(n^2)이다.

빅오 표기법의 한계

빅오 표기법은 최악의 경우 시간 복잡도를 기준으로 하기 때문에 실제 평균 성능을 완전히 반영하지 못할 수 있다. 따라서 평균 시간 복잡도도 함께 고려하여 알고리즘의 효율성을 평가해야 한다.

Explorer