기초적인 O(n) vs O(n²) 실전 예제는 Part 1 (이전 글)을 참고해주세요.
지난 포스팅에서 우리는 시간 복잡도를 통해 코드의 효율성을 판단하는 법을 배웠습니다.
그런데 공부를 하다 보면 두 가지 의문이 생깁니다.
"왜2n이나100n이나 똑같이 O(n)이라고 퉁치는 걸까?"
"Big-O 말고 오메가(Ω), 세타(Θ)는 대체 뭘까?"
오늘은 개발자 면접이나 전공 수업에서 깊이 있게 다루는 시간 복잡도의 수학적 원리를 아주 쉽게 풀어서 정리해 보겠습니다.
1. 왜 상수(Constant)는 생략하는가?
우리는 흔히 O(2n)을 O(n)으로, O(n² + 100)을 O(n²)으로 표기합니다. 2배나 차이가 나는데 왜 무시하는 걸까요?
핵심: "정확한 시간"이 아니라 "성장 패턴"이 중요하다
Big-O는 "몇 초가 걸리냐"를 재는 것이 아니라, "입력 크기(n)가 무한대로 커질 때, 연산량이 어떤 그래프 모양으로 증가하는가"
를 보는 지표이기 때문입니다.
예시 비교:
- O(n): n=1,000일 때 → 1,000번 연산
- O(2n): n=1,000일 때 → 2,000번 연산
물론 2배 차이가 나지만, n이 커질수록 "정비례해서 늘어난다(선형 증가)"는 패턴은 동일합니다. 그래프의 기울기만 다를 뿐, 모양은 직선으로 똑같죠.
생략 규칙 정리
가장 영향력이 큰 항(Dominant Term)만 남기고 나머지는 과감히 버립니다.
| 규칙 | 예시 | 결과 (Big-O) | 이유 |
|---|---|---|---|
| 상수 곱 무시 | 2n, 100n | O(n) | 단순히 기울기 차이일 뿐, 패턴 동일 |
| 낮은 차수 무시 | n² + n + 1 | O(n²) | n이 커지면 n²이 압도적으로 주도함 |
| 로그보다 n 우선 | n + log n | O(n) | log n의 증가 속도는 매우 느림 |
| 상수만 존재 | 100번 수행 | O(1) | 입력 크기와 무관하게 고정됨 |
2. Big-O (O): 상한선
우리가 가장 흔하게 쓰는 표기법입니다. 알고리즘 성능의 "최악의 상황" 혹은 "아무리 느려도 이것보단 안 느리다(상한)"는 것을 보장합니다.
수학적 정의
f(n) ≤ C · g(n)
(for sufficiently large n)
의미: f(n)의 증가 속도가 g(n)보다 빨라지지 않는다. (위에서 눌러주는 상한선)
예를 들어 f(n) = n² + n + 1 이라는 알고리즘이 있을 때, n이 충분히 크다면 C · n²보다 항상 작거나 같습니다.
따라서 이 알고리즘은 f(n) ∈ O(n²) 이라고 할 수 있습니다.
3. Big-Ω, Big-Θ: 다른 형제들
Big-O만 있는 게 아닙니다. 상황에 따라 하한선이나 정확한 구간을 표현해야 할 때도 있습니다.
Big-Ω (오메가): 하한선 (최소 성장 속도)
"아무리 빨라도 이것보단 빠를 수 없다"는 최소한의 연산량을 의미합니다.
f(n) ≥ c · g(n)
의미: f(n)의 증가 속도가 g(n)보다 느리지 않다. (아래에서 받쳐주는 하한)
예: n² + n + 1은 아무리 작아도 n² 보다는 큽니다. → f(n) ∈ Ω(n²)
Big-Θ (세타): 딱 맞는 성장 속도
상한(O)과 하한(Ω)이 같을 때, 즉 "딱 이 정도 속도로 성장한다"고 정확하게 말할 때 사용합니다.
f(n) ∈ O(g(n)) AND f(n) ∈ Ω(g(n))
의미: f(n)과 g(n)이 같은 차수로 성장한다. (샌드위치처럼 딱 맞음)
예: n² + n + 1은 n²의 상한도 만족하고 하한도 만족하므로 → f(n) ∈ Θ(n²)
4. 요약
보통 알고리즘 문제 풀이(코딩 테스트)에서는 Big-O(최악의 경우)만 고려하면 됩니다. 내가 짠 코드가 최악의 상황에서도 제한 시간 내에 통과하는지가 중요하기 때문입니다.
- O(2n) → O(n): 성장 패턴(기울기)이 선형으로 같기 때문에 상수는 무시한다.
- Big-O (O): "최악의 경우엔 이 정도야" (상한선)
- Big-Ω (Ω): "최소한 이만큼은 걸려" (하한선)
- Big-Θ (Θ): "정확히 이 정도 차수야" (평균/정확)
이제 누군가 "왜 상수를 떼고 말하나요?"라고 묻는다면, "입력 데이터가 무한대로 커질 때의 성장 패턴을 보기 위함입니다!"라고 멋지게 대답해 보세요.
'TEST > Testing' 카테고리의 다른 글
| 내 코드가 느린 이유? 시간 복잡도(Time Complexity)와 Big-O 정리_Part 1 (0) | 2025.12.08 |
|---|