Big-O 표기법 ( 점근 표기법 )
일반적으로 알고리즘의 시간복잡도를 나타내는데 사용한다.
Big-O 표기법 , Big-Omega 표기법 , Big-Theta 표기법 등이 있다.
보통 성능이 얼마나 나쁜지가 중요하므로 Big-O 표기법이 제일 많이 쓰인다.
Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간 복잡도를 가질 때 사용한다.
즉, Big-O 표기법은 입력 크기 n 이 커질 때 알고리즘의 실행 시간 ( 또는 메모리 사용량 ) 의 상한이 어떻게 증가하는지를 나타내는 점근적 ( Asymptotic ) 척도이다. 상수 시간 , 상수 배수 같은 세부 구현 차이는 무시하고 성장률만 본다는게 핵심이다.
핵심 규칙 ( 작동 원리 + 개념 요약 )
- 입력 크기 n 을 먼저 정한다 ( 예시 : 배열 길이 , 노드 수 등 )
- 합 규칙 : 연속 단계는 O ( f + g ) → O ( max ( f , g ) )
- 곱 규칙 : 중첩 단계는 O ( f x g )
- 상수, 하위항 제거 : 3n + 10 → O( n ) , n² + n → O( n² )
- 케이스 구분 : 최악 ( O ) , 평균 ( 평균적 ) , 최선 ( Ω는 하한 , Θ는 정확한 차수 )
└ 보통 최악의 상한 O(·) 을 문서화 - 로그가 생기는 때 : 매 단계에 반으로 줄이거나 ( 이분 탐색 ) , 분할할 때
- 공간복잡도도 동일한 규칙으로 분석한다 ( 스택 깊이 , 추가 배열 등 )
- 서로 다른 입력 크기는 n , m 등으로 분리해 표기한다 : O ( n + m ) , O ( nm )
- 상환 분석 : 예시 - List<T>.Add 는 평균적으로 Amortized O( 1 )
대표 복잡도 한눈표
| 복잡도 | 예시 |
| O(1) | 배열 인덱스 접근 , 해시 조회 ( 평균 ) |
| O(log n) | 이분 탐색 , 균형 이진트리 탐색 |
| O(n) | 선형 탐색 , 한 번 순회 |
| O(n log n) | 비교 기반 정렬 ( 퀵 / 병합 / 힙 ) , 균형트리 대량삽입 |
| O(n²) | 이중루프 , 단순한 중복쌍 비교 |
| O(2ⁿ) , O(n!) | 부분 집합 / 순열 전수 탐색 ( 피해야 할 영역 ) |
.Net / C# 에서 자주 쓰는 자료구조 연산
| 구조 | 접근 | 탐색 | 삽입 / 삭제 | 비고 |
| T[ ] / List<T> | O(1) | O(n) | 끝에 Add : Amortized O(1) , 중간 삽입 / 삭제 : O(n) |
Capacity 관리로 재할당 비용 줄이기 |
| LinkedList<T> | O(n) | O(n) | 위치 참조 있으면 O(1) | 캐시 지역성 불리 |
| Stack<T> / Queue<T> | - | - | Push / Pop / Enqueue / Dequeue : O(1) | FIFO / LIFO |
| Dictionary<K,V> | - | 평균 O(1) , 최악 O(n) | 평균 O(1) , 최악 O(n) | 해시 품질 / 충돌에 민감 |
| SortedDictionary<K,V> / SortedSet<K,V> | - | O(log n) | O(log n) | 정렬 유지 ( 트리 ) |
| PriorityQueue<T,TPriority> | - | - | Enqueue / Dequeue : O(log n) | 힙 기반 |
Big-O 표기법을 사용하는 이유
1. 성능 비교의 기준을 통일하기 위해
- 언어 , 하드웨어 , 구현 방식이 달라도
└ 알고리즘의 성장률 ( 효율성 ) 을 공통된 수학적 기준으로 비교할 수 있다.
예를 들어
- C# 이든 Python 이든
- 최신 CPU 이든 느린 CPU든
- 입력 크기가 커질수록 성능이 얼마나 나빠지는가? 를 객관적으로 판단 가능
2. 입력 크기 변화에 따른 확장성 ( Scalability ) 예측
- 작은 입력에서는 차이를 느끼지 못해도
└ n 이 커질수록 어떤 알고리즘이 훨씬 느려질지를 미리 알 수 있다.
예시
- O(n) → 10배 입력이면 10배 느려진다
- O(n²) → 10배 입력이면 100배 느려진다
미래에 데이터가 커질 때 어떤 코드가 병목이 될지 예측 가능하다.
3. 최적화의 우선순위를 정하기 위해
- 코드 전체를 무작정 최적화하는 대신
└ 복잡도가 높은 부분만 집중적으로 개선할 수 있다. - 예를 들어 정렬 알고리즘을 O(n²) 에서 O(n log n)으로 바꾸면 수백 배 성능 향상을 얻을 수 있다.
4. 면접 기술 평가에서 알고리즘 사고력 평가
- 코딩 테스트나 기술 면접에서는 Big-O 를 기준으로 사고하는 능력을 본다.
└ 예시 : "이 함수의 시간 복잡도는?"
└ "더 효율적으로 만들 수 있는가?" - 단순히 동작하는 코드보다, 입력 증가에 견디는 효율성을 증명할 수 있어야 한다.
5. 하드웨어나 언어의 영향을 배제한 이론적 비교
- 실행 시간은 CPU , 캐시 , 컴파일러 , 언어 런타임에 따라 달라진다.
- 하지만 Big-O 는 성장률 ( 점근적 추세 ) 만 보기 때문에 플랫폼 독립적인 분석이 가능하다.
주의할 점
- Big-O 는 "최악의 경우 상한선" 만을 의미한다.
└ 평균이나 실제 시간과 다를 수 있다. - O(1) 이라도 캐시 미스 , GC , I / O 등으로 느려질 수 있다.
- 항상 이론적 복잡도 + 실제 벤치마크를 함께 보는게 좋다
예시 코드
▼O(n) : 선형 탐색
public static int LinearSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++) // n번 비교
if (arr[i] == target) return i;
return -1;
}
▼O(log n) : 이분 탐색 ( 정렬 필요 )
public static int BinarySearch(int[] sorted, int target)
{
int lo = 0, hi = sorted.Length - 1;
while (lo <= hi) // 단계마다 절반으로 줄어듦 → log n
{
int mid = lo + ((hi - lo) / 2);
if (sorted[mid] == target) return mid;
if (sorted[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
▼O(n^2) : 이중 루프
public static int CountPairsLessThan(int[] arr, int x)
{
int count = 0;
for (int i = 0; i < arr.Length; i++)
for (int j = i + 1; j < arr.Length; j++) // 약 n(n-1)/2
if (arr[i] + arr[j] < x) count++;
return count;
}
▼O(n) : 해시로 중복 제거 ( 평균 )
public static int[] UniqueWithHash(int[] arr)
{
var set = new HashSet<int>(); // 평균 O(1) 삽입
foreach (var v in arr) set.Add(v); // 총 O(n)
var result = new int[set.Count];
set.CopyTo(result);
return result;
}
▼O(n log n) : 정렬 ( Introspective Sort → 평균 / 최악 O(n log n) )
public static void SortNumbers(int[] arr)
{
Array.Sort(arr);
}
▼ 지수 vs 선형 : 피보나치
└ O(φ^n): 중복 재귀
public static long FibSlow(int n)
{
if (n <= 1) return n;
return FibSlow(n - 1) + FibSlow(n - 2);
}
▼O(n) : 메모이제이션 / 반복
public static long FibFast(int n)
{
if (n <= 1) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++)
{
long c = a + b;
a = b; b = c;
}
return b;
}
주의할 점
- Big-O 는 상한이므로 실제 시간은 상수 / 캐시 / 메모리 할당 / GC / I / O 에 크게 좌우된다.
└ 작은 입력에선 O(n)이 O(log n)보다 빠를 수도 있다. 측정이 답이다. - 평균 vs 최악을 구분하자. 해시는 평균 O(1)이지만 충돌이 많으면 O(n)이 된다.
- 문자열 누적을 += 으로 반복하면 O(n²)으로 불어난다 → stringBuilder 사용
- List<T>.Add 는 Amortized O(1). 대량 추가전 Capacity 를 늘려 재할당 줄이기
- LINQ는 지연실행. 동일 쿼리 재열거 시 비용도 반복된다.
- 서로 다른 입력 크기 분리 : 예시 - 그래프 정점 V , 간선 E → O ( V + E )
- 재귀 깊이 = 공간복잡도에 영향. 이분탐색은 O (log n) 스택 , 피보나치는 O(n)
- 병렬화는 벽시계를 줄일 수 있지만 Big-O 차수는 그대로인 경우가 많다.
- 구현제 세부 : .NET의 Array.Sort / List<T>.Sort 는 Introsort ( 퀵 + 힙 + 삽입 ) 로 O(n log n) 보장
정리
Big-O는 입력이 커질수록 성능이 어떻게 증가하는지를 상한선으로 표현, 수학적으로 비교하기 위한 공통 언어이다.
상수는 버리고, 성장률만 보자
'📊Algorithm > BigO' 카테고리의 다른 글
| Big-O 표기법 성능 순 정리표 (0) | 2025.10.08 |
|---|