Big-O 표기법이란 무엇인가요?

Question

Big-O 표기법이란 무엇인가요?

Accepted Answer

**Big-O**는 입력 크기 **n**이 커질 때 알고리즘의 실행 시간이나 메모리가 어떻게 증가하는지를 나타냅니다. 상수와 낮은 차수의 항을 무시하고 *최악의 경우*의 점근적 동작을 포착합니다.

## 개념

우리는 정확한 연산 횟수가 아니라 증가율에 관심을 둡니다. O(2n + 5)는 그냥 **O(n)**입니다. n이 매우 커지면 상수와 더 작은 항은 더 이상 중요하지 않기 때문입니다.

## 흔한 분류

| Big-O | 이름 | 예시 |
|-------|------|---------|
| O(1) | 상수 | 배열 인덱스 조회 |
| O(log n) | 로그 | binary search |
| O(n) | 선형 | 리스트 순회 |
| O(n log n) | 선형 로그 | merge sort |
| O(n²) | 이차 | 중첩 루프 |
| O(2ⁿ) | 지수 | 단순한 부분집합 생성 |

## 예시

```python
def has_duplicate(nums):
    for i in range(len(nums)):        # 바깥 루프: n
        for j in range(i + 1, len(nums)):  # 안쪽 루프: n
            if nums[i] == nums[j]:
                return True
    return False
# 중첩 루프 -> O(n^2) 시간, O(1) 공간
```

## 함정

Big-O는 상수를 숨깁니다. 상수가 큰 O(n) 알고리즘은 작은 입력에서 O(n log n)에 질 수 있습니다. 또한 시간뿐 아니라 **공간** 복잡도도 함께 추적하세요.

## 왜 중요한가

Big-O를 사용하면 알고리즘을 실제로 실행하거나 하드웨어를 고려하지 않고도 비교할 수 있습니다.

입력이 수백 개에서 수백만 개로 커질 때 어떤 해법이 살아남을지를 예측하게 해 줍니다 — 확장되는 기능과 타임아웃이 나는 기능의 차이를 가르는 것입니다.

이는 모든 엔지니어가 성능을 추론할 때 사용하는 어휘입니다.

O(1)	상수	배열 인덱스 조회
O(log n)	로그	binary search
O(n)	선형	리스트 순회
O(n log n)	선형 로그	merge sort
O(n²)	이차	중첩 루프
O(2ⁿ)	지수	단순한 부분집합 생성