📊 Big-O 표기법 완벽 정리 – 알고리즘 성능의 기준
1. Big-O란 무엇인가?
Big-O 표기법은 **알고리즘의 효율성(시간 또는 공간 사용량)**을 수학적으로 표현하는 방식이다.
입력의 크기 n에 따라 알고리즘이 얼마나 느려질 수 있는지를 나타내며, 주로 최악의 경우를 기준으로 분석한다.
2. 왜 Big-O가 중요한가?
- 성능이 나쁜 알고리즘은 입력이 커질수록 실행 시간이 폭발적으로 증가한다.
- 코딩 테스트, 알고리즘 문제 해결, 실제 서비스 구현 모두에서 필수 요소이다.
- 성능을 비교할 때 단순한 실행 시간이 아니라 입력 크기에 따른 성능 증가율이 핵심이다.
3. Big-O의 주요 종류와 특징
표기법 | 설명 | 예시 상황 |
O(1) | 상수 시간: 입력 크기와 무관 | 배열의 인덱스 접근 |
O(log n) | 로그 시간: 절반씩 줄어드는 경우 | 이진 탐색 |
O(n) | 선형 시간: 한 번씩 순회 | 단일 for문 |
O(n log n) | 선형로그 시간 | 효율적인 정렬 (퀵, 병합) |
O(n²) | 이차 시간: 이중 반복 | 이중 for문 |
O(2ⁿ) | 지수 시간: 조합, 재귀 | 재귀적 피보나치 |
O(n!) | 팩토리얼 시간: 모든 순열 탐색 | 백트래킹 (순열) |
🚀 효율성 순서 (가장 효율적 → 가장 비효율적)
효율성 순위 | 표기법 | 설명 |
✅ 1위 | O(1) | 상수 시간 – 입력 크기와 관계 없음 (가장 빠름) |
✅ 2위 | O(log n) | 로그 시간 – 입력이 클수록 유리 (ex. 이진 탐색) |
✅ 3위 | O(n) | 선형 시간 – 한 번씩 전체 순회 |
⚠️ 4위 | O(n log n) | 선형로그 – 효율적인 정렬 알고리즘의 대표 |
⚠️ 5위 | O(n²) | 이중 반복 – 입력이 커지면 급격히 느려짐 |
❌ 6위 | O(2ⁿ) | 지수 시간 – 입력 조금만 늘어도 실행 시간 폭증 |
❌ 7위 | O(n!) | 팩토리얼 – 가능한 모든 조합을 시도 (가장 느림) |
흠.. 어떤게 제일 효율적인지 궁금해서 한번 찾아봤다!
4. Big-O 분석 요령
① 상수 제거
- O(2n) → O(n)
- O(5n²) → O(n²)
② 최고 차수만 남기기
- O(n² + n) → O(n²)
- O(n³ + n² + 1) → O(n³)
③ 중첩 반복문 분석
- 바깥/안쪽 각각 순회 → O(n²)
- 세 겹 중첩 for문 → O(n³)
5. 새로운 실전 예제와 해설
🧪 예제 1: O(1)
int GetFirst(int[] arr)
{
return arr[0];
}
- 입력 배열의 첫 번째 값을 가져오는 코드.
- 입력 크기와 관계없이 항상 1번 동작 → O(1)
🧪 예제 2: O(n)
int SumAll(int[] arr)
{
int sum = 0;
foreach (int num in arr)
{
sum += num;
}
return sum;
}
- 배열의 모든 값을 한 번씩 순회 → O(n)
🧪 예제 3: O(n²)
void PrintAllPairs(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr.Length; j++)
{
Console.WriteLine($"{arr[i]}, {arr[j]}");
}
}
}
- 이중 반복문으로 모든 쌍 출력 → O(n²)
6. 마무리 요약
- Big-O는 성능을 수치화한 언어다.
- “빠르다”는 말 대신 “O(n)”처럼 수학적으로 표현하자.
- 알고리즘을 설계할 때는 항상 "이 코드의 시간/공간 복잡도는?"을 습관처럼 따져보자.
'C#' 카테고리의 다른 글
C# - 정렬 알고리즘 – 선택, 삽입, 퀵, 병합 정렬 시간복잡도 비교 (0) | 2025.07.11 |
---|---|
C# - 시간 복잡도 vs 공간 복잡도 (2) | 2025.07.11 |
C# - TextRPGGame(Console) (0) | 2025.07.11 |
C# - StringBuilder - 문자열 성능 최적화 (6) | 2025.07.09 |
C# - Nullable 타입과 null 조건 연산자 (1) | 2025.07.09 |