코딩을 배우다 보면 “이 코드가 빠른 건지 느린 건지” 어떻게 판단해야 할지 막막할 때가 있습니다. 바로 그 기준이 되는 것이 Big-O 표기법입니다. 이 글에서는 Big-O 표기법의 개념부터 시간·공간 복잡도의 차이, 실제 코드에 적용하는 방법, 코딩 테스트 대비 활용법까지 단계별로 쉽게 정리했습니다.
목차
- Big-O 표기법이란 무엇인가?
- 시간 복잡도와 공간 복잡도: 핵심 원리 분석
- 복잡도를 알면 얻는 것들: 코드 품질이 달라진다
- 복잡도 분석 시 흔히 하는 실수와 주의점
- 실전에서 Big-O 표기법 적용하는 법
- 전문가·현업 개발자가 보는 복잡도 분석
1. Big-O 표기법이란 무엇인가?
**Big-O 표기법(Big-O Notation)**은 알고리즘의 성능을 수학적으로 표현하는 방법입니다. 입력 데이터의 크기(n)가 커질수록 알고리즘의 실행 시간이나 메모리 사용량이 어떻게 변하는지를 나타냅니다.
쉽게 비유하자면 이렇습니다. 도서관에서 책 한 권을 찾을 때, 책이 100권일 때와 100만 권일 때 걸리는 시간은 완전히 다릅니다. 책이 알파벳 순으로 정렬되어 있다면 절반씩 나눠 찾을 수 있고(이진 탐색), 정렬이 안 되어 있다면 한 권씩 다 뒤져야 합니다(선형 탐색). 이 두 방법의 차이를 수학적으로 표현한 것이 Big-O 표기법입니다.
Big-O는 **최악의 경우(Worst Case)**를 기준으로 성능을 표현합니다. “아무리 나빠도 이 정도”라는 상한선을 정하는 것이지요. 때문에 알고리즘을 설계하거나 선택할 때 신뢰할 수 있는 기준이 됩니다.
주요 Big-O 복잡도 종류
자주 등장하는 Big-O 복잡도를 빠른 순서대로 정리하면 다음과 같습니다.표기이름예시O(1)상수 시간배열 인덱스 접근O(log n)로그 시간이진 탐색O(n)선형 시간단순 반복문O(n log n)선형 로그 시간병합 정렬, 퀵 정렬(평균)O(n²)이차 시간버블 정렬, 이중 반복문O(2ⁿ)지수 시간피보나치 재귀(비최적)O(n!)팩토리얼 시간순열 탐색
O(1)이 가장 빠르고, 아래로 내려갈수록 느려집니다. 입력값 n이 1,000일 때 O(n²)은 1,000,000번 연산이 필요하지만 O(log n)은 약 10번이면 됩니다. 이 차이가 실제 서비스에서는 응답 시간의 차이로 직결됩니다.
2. 시간 복잡도와 공간 복잡도: 핵심 원리 분석
Big-O 표기법은 크게 두 가지 복잡도를 측정하는 데 사용됩니다. 바로 시간 복잡도와 공간 복잡도입니다.
시간 복잡도 — 얼마나 빠른가?
시간 복잡도는 입력 크기 n에 따라 알고리즘이 수행하는 연산의 횟수가 어떻게 늘어나는지를 나타냅니다. 실제 실행 시간(초)이 아니라 연산 횟수의 증가 패턴을 측정하기 때문에 하드웨어 성능과 무관하게 알고리즘 자체의 효율을 비교할 수 있습니다.
python# O(n) 예시 — 배열을 한 번씩 순회 def find_max(arr): max_val = arr[0] for num in arr: # n번 반복 if num > max_val: max_val = num return max_val # O(n²) 예시 — 이중 반복문 def bubble_sort(arr): n = len(arr) for i in range(n): # n번 for j in range(n - i - 1): # 또 n번 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]
시간 복잡도를 계산할 때는 다음 규칙을 따릅니다.
- 상수는 무시한다 : O(3n) → O(n)
- 낮은 차수는 무시한다 : O(n² + n) → O(n²)
- 가장 지배적인 항만 남긴다 : 입력이 커질수록 가장 큰 영향을 주는 항이 전체를 결정하기 때문
공간 복잡도 — 메모리를 얼마나 쓰는가?
공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 나타냅니다. 속도만큼 중요한 개념인데, 현업에서는 메모리가 제한된 환경(모바일 앱, 임베디드 시스템, 대용량 데이터 처리)에서 특히 중요하게 다뤄집니다.
python# O(1) 공간 복잡도 — 추가 메모리 거의 없음 def sum_array(arr): total = 0 # 변수 1개 for num in arr: total += num return total # O(n) 공간 복잡도 — 입력 크기만큼 메모리 사용 def copy_array(arr): new_arr = [] # n개 원소를 담을 새 배열 for num in arr: new_arr.append(num) return new_arr
시간과 공간은 종종 트레이드오프(Trade-off) 관계에 있습니다. 더 빠른 알고리즘을 위해 메모리를 더 쓰거나(캐싱, 동적 프로그래밍), 메모리를 아끼기 위해 속도를 일부 포기하는 선택이 자주 등장합니다.
3. 복잡도를 알면 얻는 것들: 코드 품질이 달라진다
Big-O 표기법을 이해하면 단순히 “이론을 아는 것” 이상의 실질적인 변화가 생깁니다.
코드 리뷰에서 설득력이 생긴다
“이 코드보다 저 코드가 더 좋다”고 말할 때 근거가 생깁니다. “O(n²)짜리 이중 반복문을 O(n log n) 정렬로 바꾸면 데이터가 10만 건일 때 연산이 100억 번에서 170만 번으로 줄어듭니다”처럼 구체적으로 설명할 수 있게 됩니다.
코딩 테스트 통과율이 올라간다
국내외 주요 기업(카카오, 네이버, 삼성, Google, Meta)의 코딩 테스트에서는 정답 여부뿐 아니라 시간 초과·메모리 초과 여부도 평가합니다. 문제를 보자마자 “이 접근법의 복잡도는 O(n²)인데 입력이 100만이면 시간 초과가 날 수 있다”는 판단이 빠르게 서야 합니다.
자료구조 선택이 달라진다
배열 vs 연결 리스트, 해시맵 vs 이진 탐색 트리 등 어떤 자료구조를 쓸지 결정할 때 복잡도 분석이 핵심 기준이 됩니다.자료구조탐색삽입삭제배열O(n)O(n)O(n)해시맵O(1)O(1)O(1)이진 탐색 트리O(log n)O(log n)O(log n)연결 리스트O(n)O(1)O(1)
4. 복잡도 분석 시 흔히 하는 실수와 주의점
최악의 경우만 고려하지 않는다
Big-O는 최악의 경우를 나타내지만, 실제로는 **평균 복잡도(Average Case)**가 더 중요할 때도 있습니다. 퀵 정렬의 최악 복잡도는 O(n²)이지만 평균은 O(n log n)으로, 실무에서는 병합 정렬보다 빠른 경우가 많습니다. Big-Θ(세타)와 Big-Ω(오메가)도 함께 이해해두면 좋습니다.
- Big-O : 최악의 경우 상한선
- Big-Θ(세타) : 평균적인 경우 (상한과 하한이 같을 때)
- Big-Ω(오메가) : 최선의 경우 하한선
상수를 무시했다가 실수하는 경우
이론상 O(n)이 O(n²)보다 항상 빠르지만, n이 매우 작을 때는 O(n²) 알고리즘이 상수 계수가 작아 실제로 더 빠를 수 있습니다. 예를 들어 삽입 정렬은 O(n²)이지만 거의 정렬된 작은 배열에서는 매우 효율적입니다. 현업에서는 이런 이유로 알고리즘 라이브러리들이 내부적으로 상황에 따라 다른 정렬 알고리즘을 혼용합니다(Python의 Timsort 등).
재귀 함수의 복잡도를 잘못 계산한다
재귀 알고리즘의 복잡도는 재귀 트리 또는 **마스터 정리(Master Theorem)**로 분석합니다. 피보나치 수열을 단순 재귀로 구현하면 O(2ⁿ)이지만, 메모이제이션(Memoization)을 적용하면 O(n)으로 극적으로 개선됩니다.
python# O(2ⁿ) — 단순 재귀 def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # O(n) — 메모이제이션 적용 def fib_memo(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo) return memo[n]
5. 실전에서 Big-O 표기법 적용하는 법
Big-O 표기법은 이론으로만 알면 반쪽짜리입니다. 코드를 짤 때 바로 적용하는 습관을 들이는 것이 중요합니다.
① 코드를 보면 반복문 먼저 센다
단일 반복문 → O(n), 이중 반복문 → O(n²), 반복문 안에서 절반씩 줄어드는 탐색 → O(n log n) 또는 O(log n). 이 패턴만 익혀도 대부분의 복잡도를 직관적으로 파악할 수 있습니다.
② 문제의 입력 범위를 보고 역산한다
코딩 테스트에서 입력 n의 범위가 주어지면, 허용 시간(보통 1~2초) 안에 처리 가능한 복잡도를 역산합니다.입력 크기 n가능한 최대 복잡도n ≤ 10O(n!) 가능n ≤ 100O(n³) 가능n ≤ 10,000O(n²) 가능n ≤ 1,000,000O(n log n) 권장n ≤ 100,000,000O(n) 또는 O(log n) 필요
③ 개선 여지를 찾는 루틴을 만든다
코드를 작성한 뒤 “이 반복문을 해시맵으로 대체할 수 있는가?”, “이 탐색을 이진 탐색으로 줄일 수 있는가?”를 스스로 묻는 습관을 들이면 복잡도가 자연스럽게 개선됩니다.
④ 프로파일링 도구로 실측값과 비교한다
이론적 복잡도와 실제 성능이 다를 수 있습니다. Python의 cProfile, JavaScript의 console.time(), Java의 JMH 같은 프로파일링 도구로 실제 실행 시간을 측정해 이론과 비교해보는 것이 좋습니다.
6. 전문가·현업 개발자가 보는 복잡도 분석
실리콘밸리 기업의 코딩 인터뷰 기준
Google, Meta, Amazon 등 글로벌 테크 기업의 기술 면접에서는 문제를 푼 뒤 반드시 “이 솔루션의 시간·공간 복잡도는 무엇인가요?”라는 질문이 따라옵니다. 답이 맞아도 복잡도를 설명하지 못하면 합격하기 어렵습니다. 면접관은 코드를 짜는 능력뿐 아니라 복잡도를 인식하고 개선책을 제시할 수 있는지를 봅니다.
현업에서의 실제 활용
현업 시니어 개발자들은 “평소 업무에서 Big-O를 매번 계산하진 않지만, 성능 이슈가 생겼을 때 병목 지점을 찾는 사고방식 자체가 복잡도 개념에서 나온다”고 말합니다. 특히 대용량 데이터를 다루는 백엔드, 검색 엔진, 추천 시스템 개발에서는 O(n²)과 O(n log n)의 차이가 서비스 안정성을 좌우하기도 합니다.
추천 학습 도구
- Big-O Cheat Sheet (bigocheatsheet.com) : 주요 자료구조·정렬 알고리즘의 복잡도 표 한눈에 확인
- LeetCode : 복잡도 기반 문제 풀이 연습
- Visualgo (visualgo.net) : 알고리즘 동작을 시각화해 복잡도를 직관적으로 이해
- 『알고리즘 문제 해결 전략』(구종만 저) : 국내 최고 수준의 알고리즘 입문서로 복잡도 분석 깊이 있게 다룸
결론
Big-O 표기법은 알고리즘의 성능을 객관적으로 비교하고 더 나은 코드를 작성하기 위한 필수 기초 언어입니다. 시간 복잡도와 공간 복잡도를 함께 이해하면 자료구조 선택부터 코딩 테스트 전략까지 전반적인 개발 실력이 높아집니다. 오늘 코드를 한 줄 짤 때부터 “이 반복문의 Big-O는 무엇인가?”를 스스로 물어보는 것부터 시작해보세요.
답글 남기기