입력 크기 n이 커질 때 알고리즘의 실행 시간(시간 복잡도, Time Complexity)이나 메모리(공간 복잡도, Space Complexity)가 얼마나 빨리 늘어나는지를 대략적으로 나타내는 표기. 정확한 횟수가 아니라 증가하는 모양을 본다. 그래서 상수와 작은 항은 버린다(2n + 5는 O(n)).
세는 요령
- 산술 연산, 변수 대입, 인덱스로 배열 접근, 키로 객체 접근은 상수 시간
O(1) - 반복문은 "반복 횟수 × 안에서 하는 일"이다. 중첩 반복은 곱해진다
O(log n)은 대략 n을 1 이하가 될 때까지 2로 나눈 횟수다. 매번 절반을 버리는 이진 탐색이 그렇다- 코드를 보면 "데이터가 10개면 몇 번? 100만 개면?"을 습관처럼 묻는다
자주 쓰는 연산
| 연산 | 복잡도 |
|---|---|
배열 push·pop, 인덱스 접근 | O(1) |
배열 shift·unshift, splice | O(n), 나머지 원소를 당기거나 민다 |
find·includes·indexOf·map·filter | O(n) |
sort | O(n log n) |
Map·Set·객체의 조회·추가·삭제 | 평균 O(1) |
실무에서 보이는 패턴
// O(n·m): 사용자마다 주문 전체를 훑는다
users.map(u => orders.filter(o => o.userId === u.id))
// O(n + m): 한 번 묶어 두고 조회한다
const byUser = Map.groupBy(orders, o => o.userId)
users.map(u => byUser.get(u.id) ?? [])렌더마다 도는 find 안의 find처럼 숨은 중첩이 성능 문제의 단골 원인이다. Map·Set으로 바꾸는 것이 가장 흔한 처방이다(해시 테이블, 빈도수 세기 패턴). 공간도 함께 본다. map은 새 배열을 만들어 O(n) 메모리를 더 쓴다.
복잡도가 낮다고 항상 빠른 건 아니다. n이 작으면 상수가 큰 "좋은" 알고리즘이 더 느릴 수 있다(롭 파이크의 프로그래밍 5규칙). 측정이 먼저다(섣부른 최적화). 많은 항목을 다 그리지 않는 리스트 가상화은 n 자체를 줄이는 방법이다.