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ⁿ) | 지수 | 단순한 부분집합 생성 |
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를 사용하면 알고리즘을 실제로 실행하거나 하드웨어를 고려하지 않고도 비교할 수 있습니다.
입력이 수백 개에서 수백만 개로 커질 때 어떤 해법이 살아남을지를 예측하게 해 줍니다 — 확장되는 기능과 타임아웃이 나는 기능의 차이를 가르는 것입니다.
이는 모든 엔지니어가 성능을 추론할 때 사용하는 어휘입니다.