#Big-O 표기법은 알고리즘의 성능을 평가하는 기준이자 시간 복잡도와 공간 복잡도를 표현하는 핵심 도구
빅오(Big-O) 표기법이란?
빅오(Big-O) 표기법은 입력 크기(n)가 증가할 때 알고리즘의 실행 시간(또는 메모리 사용량)이 어떻게 변하는지를 나타냄. 특히 최악의 경우를 기준으로 표현하기 때문에, 알고리즘의 한계점과 성능을 평가할 수 있음.
1. 빅오 표기법의 특징
- 입력 크기가 증가할수록 가장 큰 차수만 고려함
- 상수 항이나 작은 차수는 무시
- 알고리즘의 성능을 간단한 수식으로 표현가능
2. 빅오 표기법의 주요 종류와 예시
2-1. O(1) - 상수 시간: 입력 크기와 상관없이 실행 시간이 일정한 경우
- 예시: 배열에서 특정 인덱스 요소 접근
int value = arr[5]; // 상수 시간 O(1)
2-2. O(log n) - 로그 시간: 입력 크기가 줄어들 때마다 실행 시간이 절반으로 감소하는 경우
- 예시: 이진 탐색(Binary Search)
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) break;
else if (arr[mid] > target) high = mid - 1;
else low = mid + 1;
}
2-3. O(n log n) - 로그 선형 시간: 여러 번 분할하고 정렬하는 알고리즘
- 예시: 병합 정렬(Merge Sort)
2-4. O(n²) - 제곱 시간: 중첩 반복문이 있는 경우 입력 크기 n에 따라 실행 시간이 제곱으로 증가
- 예시: 두 배열의 모든 요소 비교
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(arr[i] + arr[j]);
}
}
* 빅오(Big-O) 표기법이 중요한 이유
- 알고리즘의 성능 평가
실행 시간이나 메모리 사용량을 수치화해서 비교 가능 - 코드 최적화
효율적인 알고리즘을 선택하면 더 빠르고 가벼운 프로그램을 생성 가능 - 대규모 데이터 처리
입력이 커질수록 차이가 극명해지기 때문에 시스템 최적화에 필수