시간·공간 복잡도 — 빅오 표기법 완전 정복

빅오 표기법이란?

빅오(Big-O)는 입력 크기 n이 매우 커질 때 알고리즘 실행 시간(또는 메모리)이 어떻게 증가하는지를 나타내는 표기법입니다. 상수와 낮은 차수 항은 무시하고 증가율만 나타냅니다.

복잡도	이름	n=100 연산 수 (대략)	예시
O(1)	상수	1	배열 인덱스 접근, 해시맵 조회
O(log n)	로그	7	이분 탐색, BST 탐색
O(n)	선형	100	배열 순회, 선형 탐색
O(n log n)	선형로그	700	병합 정렬, 힙 정렬
O(n^2)	이차	10,000	이중 반복문, 버블 정렬
O(2^n)	지수	10^30	피보나치 재귀, 부분집합
O(n!)	팩토리얼	10^157	순열 완전 탐색

시간복잡도 계산 규칙

규칙 1: 상수 무시
10000 + 5n + 3 = O(n)

규칙 2: 낮은 차수 무시
n^2 + n + 1 = O(n^2)

규칙 3: 반복문 중첩 = 곱셈
for i in range(n):          # O(n)
  for j in range(n):        # x O(n)
    ...                     # = O(n^2)

규칙 4: 반복문 병렬 = 덧셈 (큰 것만)
for i in range(n): ...      # O(n)
for i in range(m): ...      # + O(m)
                            # = O(n + m)

규칙 5: 로그 복잡도 — 절반씩 줄어들면 O(log n)
while n > 1:
  n = n // 2                # 매번 절반 → O(log n)

공간복잡도

공간복잡도 = 알고리즘이 사용하는 추가 메모리

입력 크기 제외, 알고리즘이 추가로 만드는 변수/자료구조만 계산

예시:
def sum_array(arr):     # 입력 배열 제외
  total = 0             # O(1) 변수
  for x in arr:
    total += x
  return total          # 공간복잡도 O(1)

def merge_sort(arr):    # 병합 시 임시 배열 생성
  ...                   # 공간복잡도 O(n)

재귀 함수의 공간복잡도:
def factorial(n):
  if n <= 1: return 1
  return n * factorial(n - 1)
# 호출 스택 n개 = 공간복잡도 O(n)

재귀 깊이가 깊으면 Stack Overflow 주의
Python 기본 재귀 한도: 1000
sys.setrecursionlimit(10**6) 으로 변경 가능

정렬 알고리즘 완전 비교

알고리즘	최선	평균	최악	공간	안정 정렬
버블 정렬	O(n)	O(n^2)	O(n^2)	O(1)	O
선택 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)	X
삽입 정렬	O(n)	O(n^2)	O(n^2)	O(1)	O
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	O
퀵 정렬	O(n log n)	O(n log n)	O(n^2)	O(log n)	X
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	X
카운팅 정렬	O(n+k)	O(n+k)	O(n+k)	O(k)	O

면접 단골 질문 — 퀵 정렬

Q: "퀵 정렬의 최악이 O(n^2)인데 왜 실무에서 많이 쓰나요?"

A: 세 가지 이유:
1. 평균 O(n log n)이며 상수 인자가 작다
   같은 O(n log n)인 병합 정렬보다 실제로 더 빠른 경우가 많음
   캐시 효율이 좋음 (연속 메모리 접근)

2. In-place 정렬 (공간복잡도 O(log n))
   병합 정렬은 O(n) 추가 메모리 필요
   메모리 제약이 있는 환경에서 유리

3. 최악(O(n^2)) 회피 방법이 있다
   Pivot을 무작위 선택 (Randomized Quick Sort)
   세 값의 중앙값을 Pivot으로 선택 (Median-of-Three)

실무 언어의 정렬:
Python sort(): Timsort (병합 정렬 + 삽입 정렬 혼합, O(n log n))
Java Arrays.sort(): 기본형은 Dual-Pivot 퀵 정렬, 객체는 Timsort
C++ std::sort(): Introsort (퀵 정렬 + 힙 정렬 + 삽입 정렬 혼합)

안정 정렬(Stable Sort)이란?

안정 정렬: 같은 키를 가진 원소의 상대 순서가 정렬 후에도 유지

예시:
입력: [(Kim, 3등), (Lee, 3등), (Park, 1등)]
      (Kim과 Lee는 동점)

안정 정렬 결과: [(Park, 1등), (Kim, 3등), (Lee, 3등)]
불안정 정렬 결과: [(Park, 1등), (Lee, 3등), (Kim, 3등)] 가능

안정 정렬이 중요한 경우:
- 이미 정렬된 데이터에 추가 정렬 기준 적용
- 데이터베이스 정렬, UI 목록 표시

관련 검색어  ·  빅오 표기법, 시간복잡도 계산, 정렬 알고리즘 비교, 퀵 정렬 vs 병합 정렬, 공간복잡도, 안정 정렬, 개발자 면접 복잡도