안녕하세요 컴퓨터공학 박사과정 도비입니다.
복잡도 이론은 1960~1970년대 계산 가능성과 효율성을 연구하던 수학자·컴퓨터 과학자들이 ‘문제를 어느 정도 자원으로 풀 수 있을까’를 체계적으로 비교하고 싶다는 열망에서 출발했습니다.
1974년 앨런 코밤(Alan Cobham)은 “실용적으로 계산 가능한 것의 경계는 다항시간(P) 안에 있다”는 논지를 펼쳤고, 이 흐름이 오늘날 P-NP 문제까지 이어집니다.
산업계에서는 1990년대 초 대형 검색엔진과 전자상거래 플랫폼이 등장하면서, 대용량 데이터를 다루는 개발자들이 자연스럽게 Big-O를 회화처럼 사용하기 시작했습니다.
또 하나의 전환점은 스마트폰입니다. 작은 배터리 안에서 멀티미디어·AI 연산을 소화하려면 ‘더 빠르고, 더 가벼운’ 코드가 필수였죠. 덕분에 시간 복잡도를 낮추는 알고리즘, 공간 복잡도를 줄이는 데이터구조가 활발히 연구·채택되었습니다.
과거 프로그램이 제대로 돌아가기만 해도 뿌듯했던 시절이 있었지만, 지금은 그 효율이 경쟁력을 좌우합니다. 데이터가 수십 억 건으로 늘고, 모바일·임베디드처럼 자원이 제한된 환경도 흔해졌기 때문이죠. 그래서 얼마나 빨리(시간 복잡도) 그리고 얼마나 적은 메모리로(공간 복잡도) 문제를 해결하는지가 중요합니다.
시간 복잡도(Time Complexity)
시간 복잡도(Time Complexity)는 입력 크기 N이 커질 때 알고리즘이 수행해야 하는 기본 연산 횟수의 증가율입니다.
가장 널리 쓰이는 표기법이 Big-O로, 대개 최악의 경우를 가정해 O(·)로 적습니다. 평균적인 상황은 Θ(세타), 최선의 상황은 Ω(오메가)로 나타낼 수 있지만, 현실에서는 최악을 기준으로 안전성을 확보하는 편이 일반적입니다.
공간 복잡도(Space Complexity)
공간 복잡도(Space Complexity)는 입력이 커질수록 알고리즘이 필요로 하는 메모리 양이 어떻게 변하는지를 말합니다. 여기에는 입력 데이터를 보관하는 배열·리스트, 재귀 호출 시 스택 프레임, 동적으로 할당한 임시 버퍼까지 모두 포함됩니다.
점근적 분석의 필요성
같은 코드라도 CPU 클럭·메모리 대역폭·컴파일러 최적화 수준에 따라 절대 실행시간이 크게 달라집니다. 그러나 입력 크기가 충분히 커지면 시간·공간 사용량의 증가 패턴(차수)은 하드웨어를 초월해 거의 일정합니다. 그래서 상수 배수나 하위 차수 항을 과감히 무시하고 최고 차수만 남기는 점근적(Asymptotic) 분석이 널리 쓰입니다.
자주 만나게 되는 시간복잡도
- O(1) – 해시 테이블 검색, 배열 첨자 접근
- O(log N) – 이진 탐색, 힙 연산
- O(N) – 한 번의 배열 순회, 선형 검색
- O(N log N) – 병합·힙·퀵 정렬(평균), 균형 트리 정렬
- O(N²) – 버블·선택 정렬, 2중 for 루프
- O(N³) – 플로이드-워셜, 행렬 곱 일반 알고리즘
- O(2ⁿ) – 부분집합 생성, 피보나치 순수 재귀
- O(N!) – 완전탐색(외판원 문제)
이 중 O(N log N) 이하가 ‘실제로 돌아간다’고 평가받는 영역이며, 다항시간(O(Nᵏ))은 이론적으로도 ‘계산 가능’ 범주라 부릅니다.
자주 만나게 되는 공간복잡도
• O(1) – 포인터 몇 개만 추가로 쓰는 in-place 정렬
• O(N) – 입력 수만큼 새로운 배열을 할당(예: Counting Sort)
• O(N log N) – 균형 트리 구조(예: 세그먼트 트리)
• O(N²) – 인접행렬 그래프 표현, DP 테이블(N×N)
메모리 기술이 발전하면서 공간 문제는 예전보다 덜 드러나지만, 코딩 테스트나 임베디드 환경에서는 여전히 256 MB 제한을 쉽게 만납니다. 인접행렬로 그래프 10만 개 정점을 표현하면 100,000² ≈ 10¹⁰칸이 필요해 단숨에 메모리 초과가 납니다.
복잡도 계산 실전 예시
· 단순 배낭(0/1 Knapsack) 순수 재귀
시간 O(2ⁿ), 공간 O(N) - 깊이 N의 재귀 스택만 사용
· 동적 계획법(DP) 테이블 버전
시간 O(N·W), 공간 O(N·W) - 무게 W까지 2차원 배열
· 이진 탐색
시간 O(log N), 공간 O(1) - 반복문 구현 시 추가 기억장소 없음
· 퀵 정렬 평균·최악
평균 시간 O(N log N), 최악 O(N²) - 피벗이 끝에 몰릴 수도
공간 O(log N) (재귀 스택), in-place라 추가 배열은 불필요
반복·재귀·분할정복 공식
for 루프 → 반복 횟수를 그대로 식에 곱한다
중첩 루프 → 중첩 갯수만큼 차수를 올린다
재귀 → T(N)=aT(N/b)+f(N) 형태로 변환해 마스터 정리 적용
- 예시 : 병합정렬 T(N)=2T(N/2)+N → O(N log N)
- 예시 : 퀵정렬 평균 T(N)=2T(N/2)+O(N) → O(N log N) 단, 균등 분할 가정
실제 코딩 테스트에서의 판단법
문제에 ‘N ≤ 100,000, 시간제한 1 초’라고 적혀 있다면, 일반 CPU에서 대략 1억 번 이하 연산이 필요합니다.
O(N²) 알고리즘은 10¹⁰ 번으로 시간 초과가 확실하므로, O(N log N) 이하 설계를 골라야 하죠.
메모리도 256 MB 제한이라면 int 배열 64 M 개(약 256 MB) 이상은 불가능합니다.
이런 가이드라인을 빠르게 머릿속에서 계산할수록 풀이 전략을 효율적으로 세울 수 있습니다.
실무에서의 응용
빅데이터 플랫폼은 MapReduce 단계마다 디스크 I/O를 줄이기 위해 O(N) → O(N / k) 형태의 샤딩을 활용하고, 모바일 게임 클라이언트는 메모리 풀이 날아가면 곧바로 프레임 드랍이 발생하므로 O(1) 메모리 캐싱 기법을 선호합니다.
데이터베이스 인덱스도 B-트리 덕분에 O(log N)으로 검색이 가능합니다.
결론
시간·공간 복잡도는 알고리즘 성능을 예측할 수 있는 가장 간결하면서도 강력한 도구입니다. 표만 외우기보다 실제 코드를 연산식으로 전개해보며 ‘왜 이 차수가 나오는가’를 몸에 익히는 게 중요합니다. 그렇게 하면 코드리뷰에서도 자연스럽게 ‘여기서 N log N이라 괜찮습니다’처럼 소통할 수 있습니다.
오늘 소개한 개념을 토대로 직접 구현과 성능 측정을 반복해보세요. 효율적인 코드는 결국 개발자의 시간을 절약하고, 사용자에게 더 나은 경험을 선사합니다. 즐거운 코딩 되세요!
만약, 더 궁금한 사항이 있거나 자세한 조언이 필요하시면 아래 네이버폼으로 연락주세요
도비에게 질문 남기기
네이버 폼 설문에 바로 참여해 보세요.
form.naver.com