시간·공간 복잡도

🎯 학습 목표

이 강을 마치면 다음을 할 수 있습니다.

• Big-O 표기법이 무엇이고 왜 사용하는지 직관적으로 설명할 수 있습니다.
• O(1)부터 O(2ⁿ)까지 각 복잡도 클래스의 의미와 실제 예시를 말할 수 있습니다.
• 코드를 보고 시간·공간 복잡도를 즉시 도출할 수 있습니다.
• 면접에서 복잡도 질문에 구조적으로 답변할 수 있습니다.

📐 Big-O 표기법이란 무엇인가

이 섹션에서는 Big-O 표기법의 정의와 직관적인 의미를 살펴보겠습니다.

알고리즘을 평가하는 가장 중요한 기준은 입력 크기(n)가 커질수록 실행 시간과 메모리가 얼마나 증가하는가입니다. 이것을 표현하는 표준 언어가 Big-O 표기법입니다. Big-O는 "최악의 경우(worst case)"에 알고리즘이 필요한 연산 수의 상한을 나타냅니다.

Big-O를 쓰는 이유는 컴퓨터마다 CPU 속도가 다르고 프로그래밍 언어마다 실행 속도가 달라서, 절대적인 시간(초)으로 알고리즘을 비교하면 의미가 없기 때문입니다. n이 10에서 100만으로 커졌을 때 시간이 어떻게 변하는가 — 이 "성장률"로 비교하는 것이 공정하고 일관됩니다.

관련 표기법 3가지의 차이도 알아두세요. Big-O(O)는 상한(최악), Big-Ω(오메가)는 하한(최선), Big-Θ(세타)는 평균(상한과 하한이 같은 경우)을 나타냅니다. 면접에서는 거의 항상 Big-O를 기준으로 이야기합니다. 면접관이 "이 알고리즘의 시간복잡도가 무엇인가요?"라고 물으면 최악의 경우를 기준으로 답하면 됩니다.

Big-O 계산에서 상수는 무시합니다. 예를 들어 O(3n)은 O(n)으로, O(n²+n)은 O(n²)으로 표기합니다. 가장 빠르게 증가하는 항만 남기는 것이 규칙입니다. n이 충분히 커지면 낮은 차수의 항들은 무의미해지기 때문입니다.

📊 복잡도 클래스 완전 정리 — O(1)부터 O(2ⁿ)까지

이 섹션에서는 기술 면접에서 반드시 알아야 하는 복잡도 클래스들을 직관적으로 이해하는 방법을 살펴보겠습니다.

표기	이름	n=1000일 때 연산	대표 예시
O(1)	상수	1	배열 인덱스 접근, 해시맵 탐색
O(log n)	로그	~10	이진 탐색, 균형 BST 탐색
O(n)	선형	1,000	배열 순회, 선형 탐색
O(n log n)	선형로그	~10,000	병합 정렬, 퀵 정렬(평균)
O(n²)	이차	1,000,000	버블 정렬, 이중 반복문
O(2ⁿ)	지수	10³⁰¹ (불가)	피보나치 재귀, 부분집합
O(n!)	팩토리얼	무한대 (불가)	순열 모두 나열

각 복잡도를 직관적으로 이해하는 방법입니다.

O(1) — 상수 시간: 입력 크기가 아무리 커도 연산 횟수가 변하지 않습니다. 배열에서 arr[5]로 접근하면 n이 10이든 100만이든 똑같이 한 번의 연산입니다. 메모리 주소 계산 한 번으로 바로 접근하기 때문입니다.

O(log n) — 로그 시간: 매 단계마다 문제 크기가 절반으로 줄어드는 경우입니다. 이진 탐색에서 1000개 배열에서 찾으려면 최대 10번(log₂1000 ≈ 10) 비교합니다. n이 100만이 되어도 20번 비교로 끝납니다. 로그 시간은 매우 효율적인 복잡도입니다.

O(n) — 선형 시간: 입력 크기에 비례하는 연산입니다. 배열 전체를 한 번 순회하면 O(n)입니다. n이 1000이면 1000번, 100만이면 100만 번 연산합니다. 선형 시간은 대부분의 경우 합격 가능한 복잡도입니다.

O(n log n) — 선형로그 시간: 선형보다 조금 느리지만 이차보다 훨씬 빠릅니다. 병합 정렬과 힙 정렬이 이 복잡도입니다. 대부분의 정렬 알고리즘의 최적 복잡도가 O(n log n)이며, 이것보다 빠른 비교 기반 정렬은 이론적으로 불가능합니다.

O(n²) — 이차 시간: 이중 반복문에서 전형적으로 나타납니다. n=1000이면 100만 번 연산, n=100만이면 1조 번 연산입니다. 작은 입력에서는 괜찮지만 n이 10만 이상이면 실용적으로 너무 느립니다. 버블 정렬, 삽입 정렬, 모든 쌍을 비교하는 알고리즘이 여기에 해당합니다.

O(2ⁿ) — 지수 시간: n이 50만 넘어도 이미 1조 번 이상 연산합니다. 피보나치를 재귀로 단순하게 구현하면 O(2ⁿ)이 됩니다. 이 복잡도는 실용적으로 사용 불가능하며, 메모이제이션이나 동적 프로그래밍으로 O(n)으로 줄일 수 있습니다.

🔎 코드에서 복잡도 도출하는 법

이 섹션에서는 주어진 코드를 보고 시간복잡도를 즉시 분석하는 방법을 살펴보겠습니다.

면접에서 "이 코드의 시간복잡도는?"이라고 물으면 코드를 보고 즉시 답해야 합니다. 다음 규칙만 알면 대부분의 경우를 처리할 수 있습니다.

규칙 1 — 반복문의 복잡도

단순 반복문(n번 반복) → O(n). 이중 반복문(n번 × n번) → O(n²). 삼중 반복문 → O(n³). 주의할 점은 이중 반복문이더라도 안쪽 반복이 외부 반복에 종속되지 않으면 O(n²)이 아닐 수 있습니다. 예를 들어 바깥 반복이 n번이고 안쪽 반복이 항상 상수(k)번이면 O(n×k) = O(n)입니다.

규칙 2 — 절반씩 줄어드는 반복

매 반복마다 탐색 범위가 절반으로 줄어들면 O(log n)입니다. 이진 탐색이 대표적입니다. while(left <= right) 형태에서 mid를 기준으로 왼쪽 또는 오른쪽만 탐색하면 반복 횟수가 log₂n에 수렴합니다.

규칙 3 — 재귀의 복잡도

재귀 함수의 복잡도는 (재귀 호출 수) × (각 호출의 비용)으로 계산합니다. 피보나치 재귀(f(n) = f(n-1) + f(n-2))는 각 호출이 두 번 재귀하므로 O(2ⁿ)입니다. 반면 이진 탐색 재귀는 한 번에 절반으로 줄이므로 O(log n)입니다. 병합 정렬은 n/2씩 두 번 나누고(O(log n) 레벨) 각 레벨에서 O(n) 병합을 하므로 O(n log n)입니다.

규칙 4 — 순차 실행

두 코드 블록이 순차적으로 실행되면 O(n) + O(n²) = O(n²)처럼 큰 쪽이 지배합니다. "덧셈이 아닌 최대값"으로 생각하세요.

🧠 공간복잡도와 시간-공간 트레이드오프

이 섹션에서는 시간복잡도만큼 중요한 공간복잡도와, 두 가지를 맞바꾸는 트레이드오프 전략을 살펴보겠습니다.

공간복잡도(Space Complexity)는 알고리즘이 실행되는 동안 사용하는 추가 메모리의 양입니다. 입력 데이터 자체는 포함하지 않고, 알고리즘이 별도로 사용하는 메모리만 카운트합니다(보조 공간).

공간복잡도 예시입니다. 변수 몇 개만 사용하는 경우(투 포인터, 반복문 변수) → O(1). 입력 크기에 비례하는 배열이나 해시맵을 만드는 경우 → O(n). 재귀 함수는 호출 스택을 사용하므로 재귀 깊이만큼 공간이 필요합니다. 깊이가 n이면 O(n), 이진 탐색 재귀는 O(log n)의 스택 공간을 사용합니다.

시간-공간 트레이드오프는 시간을 줄이기 위해 메모리를 더 사용하거나, 메모리를 아끼기 위해 시간이 더 걸리는 선택입니다. 이것이 알고리즘 최적화의 핵심입니다.

가장 대표적인 예가 메모이제이션입니다. 피보나치를 단순 재귀로 구현하면 O(2ⁿ) 시간이지만 O(n) 공간(결과 저장 배열)을 추가하면 O(n) 시간으로 줄어듭니다. 시간을 지수에서 선형으로 줄이는 대신 O(n) 공간을 소비하는 트레이드오프입니다.

또 다른 예가 해시맵 활용입니다. 배열에서 두 수의 합을 찾는 문제를 이중 반복문으로 풀면 O(n²) 시간·O(1) 공간이지만, 해시맵을 사용하면 O(n) 시간·O(n) 공간으로 해결됩니다. 공간을 희생해서 시간을 줄이는 전형적인 패턴입니다.

면접에서 이 트레이드오프를 언급하는 것은 매우 좋은 평가를 받습니다. "이 방법은 O(n) 시간이지만 O(n) 공간을 사용합니다. 메모리가 제한된 환경이라면 O(n²) 시간·O(1) 공간 방법도 있는데, 어떤 것을 선호하시나요?"처럼 질문으로 연결하면 더 좋습니다.

🗣️ 면접에서 복잡도를 설명하는 언어

이 섹션에서는 알고 있는 것을 면접에서 자신 있게 표현하는 언어와 구조를 살펴보겠습니다.

복잡도를 분석할 수 있어도 면접에서 어떻게 말해야 할지 모르면 손해입니다. 다음 구조로 일관되게 말하면 전문적으로 보입니다.

표준 복잡도 답변 구조

"이 알고리즘의 시간복잡도는 O(n log n)입니다. n개의 원소를 병합 정렬로 처리하는데, 재귀 분할이 log n 레벨로 이루어지고 각 레벨에서 n번의 병합 연산이 필요하기 때문입니다. 공간복잡도는 O(n)입니다. 병합 과정에서 임시 배열이 필요하기 때문입니다. 만약 공간을 O(1)로 줄이고 싶다면 힙 정렬을 사용할 수 있는데, 시간복잡도는 동일하게 O(n log n)을 유지합니다."

이 구조는 세 가지를 포함합니다. ① 결론 먼저(복잡도 표기), ② 근거(왜 그런지), ③ 트레이드오프(다른 방법과 비교). 이 세 가지만 포함하면 어떤 복잡도 질문에도 만족스러운 답변이 나옵니다.

복잡도 분석 중 자주 실수하는 것들도 알아두세요.

• 평균과 최악 혼동: 퀵 정렬은 평균 O(n log n)이지만 최악 O(n²)입니다. 면접에서는 두 가지를 모두 언급하고 피벗 선택 전략으로 최악을 피하는 방법을 언급하면 심화 답변이 됩니다.
• 상수 계수 포함: "O(2n)"이나 "O(3n²)" 같은 표기는 Big-O에서는 "O(n)", "O(n²)"로 간소화합니다. 상수를 포함해 말하면 이해가 부족한 것으로 보입니다.
• 공간복잡도 미언급: 면접관이 시간복잡도만 물어봐도 "공간복잡도는 O(n)입니다"라고 덧붙이면 좋은 인상을 줍니다. 공간까지 신경 쓰는 개발자임을 보여주기 때문입니다.

📝 핵심 요약

5강에서 배운 내용을 정리해 보겠습니다.

복잡도	직관	대표 알고리즘	n=1000 연산 수
O(1)	항상 1번	배열 접근, 해시맵	1
O(log n)	절반씩 줄어듦	이진 탐색, BST	~10
O(n)	한 번 순회	선형 탐색	1,000
O(n log n)	순회 × 로그	병합 정렬, 힙 정렬	~10,000
O(n²)	이중 순회	버블 정렬	1,000,000
O(2ⁿ)	매 단계 2배	피보나치 재귀	10³⁰¹

복잡도 답변 핵심: ① 결론(표기) → ② 근거(왜) → ③ 트레이드오프(다른 방법). 다음 강인 6강 — 코딩 테스트 실전 전략에서는 프로그래머스·백준에서 실전 점수를 높이는 전략, 시간 배분법, 언어별 팁, 자주 쓰이는 내장 함수와 라이브러리를 완전히 정리합니다. 알고리즘 지식만큼 시험장 전략도 중요합니다!