- 빅오 표기법은 함수 성능을 입력 크기 변화에 따른 성장 양상으로 표현함
- 글에서는 대표적으로 상수, 로그, 선형, 제곱 항목의 빅오를 예시와 함께 설명함
- 자료구조 및 알고리듬에 따라 시간복잡도가 다르며 입력 배열 정렬, 탐색 등에서 차이를 보임
- 실제 코드 성능 개선을 위해서는 적절한 데이터 구조 선택과 반복문 내 불필요 연산 제거가 핵심임
- 빅오는 항상 입력과 실행 시간의 관계를 가장 단순화시켜 나타내며, 성능 개선시 코드를 직접 측정하는 것이 중요함
빅오 표기법 개요
- 빅오 표기법은 시간 측정 대신 입력 크기(n)에 따른 실행 시간의 성장 양상을 설명하는 방법임
- 함수 실행 시간을 입력 크기에 따라 분류하며 주로 상수(O(1)) , 로그(O(log n)) , 선형(O(n)) , 제곱(O(n²)) 형태가 분석 대상임
- 이 글은 초심자도 이해할 수 있도록 각 항목의 개념과 시각적 사례, 실제 코드 예시를 통해 설명함
반복(Iterating)과 선형 알고리듬
sum(n)함수는 1에서 n까지 더하는 반복 구조 예시로, 입력값 n이 커질수록 수행 시간도 정비례로 증가함- 실제로
sum(1e9)은 약 1초,sum(2e9)은 약 2초 소요로 벽시계 시간(wall-clock time)이 O(n) 패턴으로 성장함 - 시간복잡도는 함수 입력과 실행 시간의 관계이며, 이를 빅오 표기법으로 표현함(O(n) — n에 비례)
- 반복 대신 수학 공식을 활용한
sum(n) = (n*(n+1))/2은 실행 시간이 입력값 n과 무관하게 일정(상수) 함 - 이런 함수는 상수 시간복잡도 O(1) 라고 하며, 입력값 변화에 따른 실행 시간 성장 없음이 특징임
빅오 표기법 문법
- 빅오의 O는 “Order(성장 차수)”에서 유래하며, 성장 형태 자체만을 표시
- 실제 실행 시간의 절대값이 아니라 입력 대비 성장의 '패턴'만을 간결히 표기함
- 예를 들어 O(n) 함수라도 'O(2n)'이나 'O(n+1)'처럼 복잡하게 적지 않고, 가장 단순한 항만 선택
입력 구성을 이용한 시간 단축
sum(n)공식 예시처럼 알고리듬 개선을 통해 시간복잡도가 O(n)에서 O(1)로 변환 가능- 다만, 상수 시간복잡도라고 무조건 빠른 것은 아니며, 어떤 연산일지에 따라 실행시간 전체는 달라질 수 있음
- O(n) 알고리듬이 특정 입력에서는 O(1)보다 빠를 수 있으나, 입력 크기가 커지면 항상 O(1) 방식이 우세해짐
정렬(Sorting)과 제곱(Quadratic) 알고리듬: 버블 정렬 예시
- 버블 정렬(Bubble Sort) 은 인접 수 교환을 반복하며 배열을 정렬하는 기본 예시임
- 이미 정렬된 경우는 1회 반복(O(n)), 역순은 반복적으로 n회 순회 필요 → 최악의 경우 전체 연산 수 n²
- O(n²) 알고리듬은 입력이 커질수록 실행 시간이 제곱 형태로 크게 증가
- 실제 활용에서 빅오는 항상 최악의 경우(worst-case) 기준임(단, 경우에 따라 평균/최선도 표기)
- 배열 초기 상태에 따라 반복 회수가 줄어들기도 하지만, 최악 케이스 고려로 항상 제곱 시간복잡도로 분류
탐색(Searching)과 로그 알고리듬: 이진 탐색 예시
- 이진 탐색(Binary Search) 은 정렬된 범위의 중앙값을 추정하고, 매 단계마다 후보 영역을 절반씩 소거함
- 예를 들어 1~100 사이 특정 수 맞추기에 최대 7회, 1~10억까지도 31회 미만 시도로 가능
- 매 단계마다 후보 리스트가 반씩 줄어드는 구조로 실행 시간은 O(log n) (로그 시간복잡도)임
- 로그형 알고리듬은 n이 커질 때 증가 속도가 굉장히 느린 형태를 보임(선형 또는 제곱에 비해 월등히 효율적)
- 그래프 비교 시 log n, n, n²순으로 성장 차이가 극명하게 드러남
실제 적용: 시간복잡도 개선 팁
리스트에서 항목 찾기
- 기본적으로 배열에서 값을 찾는 함수는 O(n) 에 해당함
- 빈번하게 탐색하는 경우, Set과 같은 자료구조를 사용하면 O(1) 로 향상 가능
- 단,
new Set(array)로 변환하는 과정 자체가 O(n) 이므로 빈번 조회에만 적절함(변환 비용 고려) - 예:
items.has("banana")는 상수 시간복잡도를 제공
인덱스 활용 반복문 작성
-
아래와 같이 반복문 내부에서
.indexOf를 사용하는 코드가 흔히 성능 문제의 원인임function buildList(items) { const output = []; for (const item of items) { const index = items.indexOf(item); output.push(`Item ${index + 1}: ${item}`); } return output.join("\n"); } -
.indexOf는 루프 내에서 O(n) 연산이기 때문에, 전체적으로 O(n^2) 패턴이 됨 -
인덱스 기반 반복 또는
forEach((item, index) => ...)활용 시 O(n) 으로 개선됨function buildList(items) { const output = []; for (let i = 0; i < items.length; i++) { output.push(`Item ${i + 1}: ${items[i]}`); } return output.join("\n"); }
메모이제이션(Memoization) 활용
-
팩토리얼과 같이 반복 호출 시 중복 계산되는 구조는 결과 캐싱(Map 활용) 을 적용하여 성능 향상 가능
-
Map에서의 조회는 O(1) 에 해당하여 불필요 재계산 최소화 -
단, 캐싱은 평균 시간 개선에 기여하며, 최악 시간복잡도 자체는 변하지 않아도 효율적 성능 향상 가능
const cache = new Map(); function factorial(n) { if (cache.has(n)) { return cache.get(n); } if (n === 0) { return 1; } const result = n * factorial(n - 1); cache.set(n, result); return result; }
성능 평가와 결론
- 코드 성능 개선 시 이론상 시간복잡도와 함께 직접 실행 테스트로 실제 개선 여부를 확인해야 함
- 빅오는 입력과 실행 시간의 관계와 성장 패턴을 가장 본질적으로 단순화해서 표현함
- 좋은 알고리듬 선택 및 데이터 구조 최적화로 코드 효율성을 극대화할 수 있음
요약 정리
- 빅오 표기법은 함수 입력값과 실행 시간의 관계를 표현
- 주요 성능 등급: O(1) (상수), O(log n) (로그), O(n) (선형), O(n^2) (제곱)
- 효율적 코드 작성 위해서는 적절한 알고리듬과 반복문 최적화가 중요
- 실제 성능은 직접 측정해 개선 여부를 검증 필요
- 성장 패턴 비교 그래프를 활용해 시간복잡도 특성을 한눈에 파악 가능