다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?
실무와 알고리즘 분석에서 "최악의 경우를 보장" 하는 것이 가장 실용적이기 때문입니다.
이유 1. 안전한 성능 보장
소프트웨어는 항상 최악의 입력을 가정해야 합니다.
Ω(1) "최소한 이 정도는 걸린다" → 낙관적, 실용성 낮음
Θ(n) "정확히 이만큼 걸린다" → 항상 성립하지 않음
O(n) "최대 이만큼 걸린다" → 최악을 보장 → 실용적 O
이유 2. Θ는 항상 구하기 어렵다
Θ는 최선과 최악이 일치할 때만 성립하는데, 대부분의 알고리즘은 입력에 따라 성능이 달라집니다.
| 알고리즘 | 최선 | 최악 | Θ 표현 가능? |
|---|---|---|---|
| 선형 탐색 | Ω(1) | O(n) | X |
| 퀵 정렬 | Ω(n log n) | O(n²) | X |
| 병합 정렬 | Ω(n log n) | O(n log n) | O Θ(n log n) |
| 배열 합산 | Ω(n) | O(n) | O Θ(n) |
이유 3. Ω는 의미가 약하다
하한선은 "적어도 이것보단 낫다" 는 의미라 성능 보장에 활용하기 어렵습니다.
선형 탐색의 하한 = Ω(1)
버블 정렬의 하한 = Ω(1)
→ 둘 다 Ω(1)이지만 실제 성능은 전혀 다름
→ 비교·보장 수단으로 부적합
정리
알고리즘을 선택할 때 중요한 질문은 "얼마나 빠를 수 있어?" X "최대 얼마나 느려질 수 있어?" O
Big-O는 이 질문에 가장 명확하게 답하기 때문에 표준으로 사용됩니다.