시간 복잡도와 공간 복잡도 완전 정복 — Big-O 표기법부터 실전 분석까지

시간 복잡도와 공간 복잡도, 왜 알아야 하나요?

• 같은 결과를 내는 코드가 두 개 있는데, 하나는 입력 10만 건에 0.1초, 다른 하나는 10분이 걸립니다
• "느리다"는 느낌만으로는 왜 느린지, 입력이 더 커지면 얼마나 나빠질지 말할 수 없습니다
• 면접에서도, 코드 리뷰에서도, 설계 단계에서도 **"이 알고리즘이 입력 크기에 따라 얼마나 느려지는가"**를 공유할 공통 언어가 필요합니다

시간 복잡도와 공간 복잡도는 알고리즘이 소비하는 시간과 메모리가 입력 크기에 따라 어떻게 증가하는지를 표현하는 도구입니다. 이 글에서는 Big-O 표기법의 정의부터, 대표적인 복잡도 등급, 공간 복잡도의 개념, 그리고 실전에서 복잡도를 분석하는 패턴까지 정리합니다.

Phase 1. Big-O 표기법 — 증가 속도를 표현하는 방법

정의

Big-O는 입력 크기 n이 충분히 커졌을 때, 알고리즘의 연산 횟수(또는 메모리 사용량)가 최대 얼마나 빠르게 증가하는지를 나타냅니다.

함수 f(n)에 대해 f(n) = O(g(n))이란, 충분히 큰 n에서 f(n) ≤ c · g(n)을 만족하는 양의 상수 c와 n₀가 존재한다는 뜻입니다.

쉽게 말하면, 입력이 커질 때 연산 횟수가 g(n)보다 빠르게 늘어나지 않는다는 의미입니다.

왜 상수와 낮은 차수 항을 버리나요?

어떤 알고리즘이 정확히 3n² + 5n + 10번 연산한다고 합시다.

n	3n²	5n	10	합계	n² 항 비율
10	300	50	10	360	83%
100	30,000	500	10	30,510	98%
10,000	300,000,000	50,000	10	300,050,010	99.98%

n이 커질수록 n² 항이 전체를 지배합니다. 상수 3이나 5n, 10은 증가 추세에 영향을 주지 않습니다. 그래서 3n² + 5n + 10 = O(n²)으로 표기합니다.

Big-O는 "정확한 연산 횟수"가 아니라 "증가 속도의 등급"을 비교하는 도구입니다.

Big-O, Big-Ω, Big-Θ

Big-O만으로는 상한만 알 수 있습니다. 실제로는 세 가지 표기가 있습니다.

표기	의미	비유
O(g(n))	최악의 경우에도 g(n) 이하 (상한)	"아무리 느려도 이 정도"
Ω(g(n))	최선의 경우에도 g(n) 이상 (하한)	"아무리 빨라도 이 정도"
Θ(g(n))	상한과 하한이 같은 등급 (정확한 등급)	"정확히 이 등급"

실무와 면접에서는 대부분 최악의 경우 상한인 Big-O를 기준으로 이야기합니다. 이 글에서도 Big-O를 기본으로 사용합니다.

참고: Big-O를 "최악의 경우"와 혼동하기 쉽지만, 엄밀히 다릅니다. Big-O는 수학적 상한 표기이고, "최악의 경우"는 입력 조건입니다. 예를 들어, 퀵소트의 평균 시간 복잡도는 O(n log n)이고, 최악 시간 복잡도는 O(n²)입니다. 둘 다 Big-O로 표기하지만 기준 입력이 다릅니다.

Phase 2. 대표적인 시간 복잡도 — 느린 것부터 빠른 것까지

입력 크기 n에 따른 대표 복잡도를 빠른 순서로 정리합니다.

O(1) — 상수 시간

입력 크기와 관계없이 연산 횟수가 일정합니다.

fun getFirst(arr: IntArray): Int {
    return arr[0]
}

배열 크기가 100이든 100만이든 한 번입니다. 배열 인덱스 접근, HashMap의 get/put(평균), 스택의 push/pop이 대표적입니다.

O(log n) — 로그 시간

한 단계마다 탐색 범위가 절반으로 줄어듭니다.

fun binarySearch(arr: IntArray, target: Int): Int {
    var lo = 0
    var hi = arr.size - 1

    while (lo <= hi) {
        val mid = (lo + hi) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target  -> lo = mid + 1
            else               -> hi = mid - 1
        }
    }
    return -1
}

n = 1,000,000이어도 log₂(1,000,000) ≈ 20번이면 끝납니다. 이진 탐색, 균형 이진 탐색 트리의 조회가 대표적입니다.

O(n) — 선형 시간

입력 전체를 한 번 훑습니다.

fun sum(arr: IntArray): Int {
    var total = 0
    for (num in arr) {
        total += num
    }
    return total
}

배열 전체 순회, LinkedList에서 특정 값 검색, 단순 집계가 여기에 해당합니다.

O(n log n) — 선형 로그 시간

전체를 훑되, 각 단계에서 분할이 일어나는 패턴입니다.

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr

    val mid = arr.size / 2
    val left = mergeSort(arr.sliceArray(0 until mid))
    val right = mergeSort(arr.sliceArray(mid until arr.size))
    return merge(left, right)
}

배열을 반씩 나누는 단계가 log n번, 각 단계에서 n개를 합치므로 O(n log n)입니다. 머지 소트, 힙 소트, 퀵소트(평균)가 대표적입니다.

참고: 비교 기반 정렬의 이론적 하한은 Ω(n log n)입니다. 비교만으로는 이보다 빠르게 정렬할 수 없다는 뜻입니다.

O(n²) — 이차 시간

이중 반복문이 대표적입니다.

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n) {
        for (j in 0 until n - 1 - i) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

모든 쌍을 비교하는 버블 정렬, 선택 정렬, 삽입 정렬(최악)이 여기에 해당합니다. n = 10,000이면 약 10^8번 연산이며, 이 근처부터 체감 속도가 급격히 느려집니다.

O(2^n) — 지수 시간

입력이 하나 늘 때마다 연산량이 두 배가 됩니다.

fun fibonacci(n: Int): Int {
    if (n <= 1) return n
    return fibonacci(n - 1) + fibonacci(n - 2)
}

위 코드에서 fibonacci(50)은 호출 횟수가 약 2^50 ≈ 10^15에 달합니다. 메모이제이션 없이는 현실적으로 불가능합니다. 부분 집합 열거, 일부 백트래킹 문제가 이 범주에 들어갑니다.

O(n!) — 팩토리얼 시간

모든 순열을 시도하는 경우입니다.

fun permutations(arr: IntArray, start: Int = 0) {
    if (start == arr.size - 1) {
        // 하나의 순열 처리
        return
    }
    for (i in start until arr.size) {
        arr[start] = arr[i].also { arr[i] = arr[start] }
        permutations(arr, start + 1)
        arr[start] = arr[i].also { arr[i] = arr[start] }
    }
}

n = 20이면 20! ≈ 2.4 × 10^18입니다. 외판원 문제(TSP)의 브루트포스가 대표적입니다.

증가 속도 비교

n이 커질수록 등급 간 차이가 극적으로 벌어집니다.

n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2^n)
10	1	3	10	33	100	1,024
100	1	7	100	664	10,000	1.27 × 10³⁰
1,000	1	10	1,000	9,966	1,000,000	—
100,000	1	17	100,000	1,660,964	10¹⁰	—

O(n²)까지는 n이 수만 이하면 실용적이지만, O(2^n) 이상은 n = 30~40만 넘어도 현실적으로 불가능합니다.

Phase 3. 공간 복잡도 — 메모리도 자원이다

공간 복잡도란

시간 복잡도가 "연산 횟수의 증가 속도"라면, 공간 복잡도는 **"추가로 사용하는 메모리의 증가 속도"**입니다. 입력 자체를 저장하는 공간은 제외하고, 알고리즘이 추가로 할당하는 메모리만 셉니다. 이 추가 메모리를 **보조 공간(auxiliary space)**이라고 부릅니다.

O(1) 공간 — 변수 몇 개

fun findMax(arr: IntArray): Int {
    var max = arr[0]
    for (num in arr) {
        if (num > max) max = num
    }
    return max
}

max 변수 하나만 추가로 사용합니다. 배열 크기가 커져도 추가 메모리는 일정하므로 O(1)입니다. 이런 알고리즘을 제자리(in-place) 알고리즘이라고 합니다.

O(n) 공간 — 입력 크기에 비례하는 자료 구조

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    for ((i, num) in nums.withIndex()) {
        val complement = target - num
        if (map.containsKey(complement)) {
            return intArrayOf(map[complement]!!, i)
        }
        map[num] = i
    }
    return intArrayOf()
}

HashMap에 최대 n개의 원소가 들어가므로 O(n) 공간입니다.

재귀의 공간 복잡도 — 콜 스택도 메모리다

재귀 호출은 콜 스택에 프레임을 쌓습니다. 최대 재귀 깊이가 곧 공간 복잡도에 포함됩니다.

fun factorial(n: Int): Long {
    if (n <= 1) return 1
    return n * factorial(n - 1)
}

factorial(10000)은 콜 스택에 10,000개의 프레임이 쌓입니다. 공간 복잡도는 O(n)입니다.

이진 탐색의 재귀 버전은 최대 log n 깊이까지 내려가므로 O(log n) 공간입니다. 반복문 버전은 콜 스택을 쓰지 않아 O(1)입니다. 같은 알고리즘이라도 구현 방식에 따라 공간 복잡도가 달라질 수 있습니다.

시간-공간 트레이드오프

시간을 줄이려면 메모리를 더 쓰고, 메모리를 아끼려면 시간이 더 드는 경우가 많습니다.

문제	시간 우선 (시간 / 공간)	공간 우선 (시간 / 공간)
중복 원소 찾기	HashSet 탐색: O(n) / O(n)	정렬 후 인접 비교: O(n log n) / O(1)
피보나치	메모이제이션: O(n) / O(n)	변수 두 개로 반복: O(n) / O(1)
Two Sum	HashMap: O(n) / O(n)	이중 반복: O(n²) / O(1)

어떤 쪽이 정답인지는 제약 조건에 따라 다릅니다. 메모리가 넉넉하면 시간을 줄이는 쪽이 유리하고, 메모리 제한이 빡빡하면 공간을 아끼는 풀이가 필요합니다. Increasing Triplet Subsequence 풀이에서 O(n) / O(n) 풀이를 O(n) / O(1)로 줄여 나가는 과정이 이 트레이드오프의 좋은 예시입니다.

Phase 4. 실전에서 복잡도를 분석하는 패턴

패턴 1: 단순 반복문

for (i in 0 until n) {
    // O(1) 작업
}

O(n)입니다. 반복 횟수가 곧 시간 복잡도입니다.

패턴 2: 중첩 반복문

for (i in 0 until n) {
    for (j in 0 until n) {
        // O(1) 작업
    }
}

바깥 n × 안쪽 n = O(n²)입니다. 안쪽 루프가 m번이면 O(n × m)입니다.

패턴 3: 반씩 줄어드는 반복

var x = n
while (x > 0) {
    x /= 2
}

n → n/2 → n/4 → ... → 1이므로 O(log n)입니다.

패턴 4: 분할 정복 재귀

fun solve(arr: IntArray, lo: Int, hi: Int) {
    if (lo >= hi) return
    val mid = (lo + hi) / 2
    solve(arr, lo, mid)
    solve(arr, mid + 1, hi)
    merge(arr, lo, mid, hi) // O(n) 작업
}

각 레벨에서 총 O(n) 작업, 레벨 수 O(log n) → O(n log n)입니다.

참고: 이 형태는 **마스터 정리(Master Theorem)**로 일반화할 수 있습니다. T(n) = aT(n/b) + O(n^d) 형태의 재귀식에서 a, b, d의 관계로 복잡도를 바로 결정합니다. 위 예시는 a = 2, b = 2, d = 1이고, a = b^d이므로 O(n^d · log n) = O(n log n)입니다.

패턴 5: 재귀 호출이 여러 갈래로 폭발하는 경우

fun fib(n: Int): Int {
    if (n <= 1) return n
    return fib(n - 1) + fib(n - 2)
}

매 호출마다 두 갈래로 분기하고, 깊이는 n입니다. 호출 트리의 노드 수는 O(2^n)입니다.

복잡도 판단 체크리스트

코드를 읽을 때 다음 질문을 던져 보면 복잡도를 빠르게 잡을 수 있습니다.

1. 반복문이 몇 겹인가? — 1겹 O(n), 2겹 O(n²), 3겹 O(n³)
2. 반복마다 범위가 절반으로 줄어드는가? — O(log n)
3. 재귀가 있다면, 한 호출에서 몇 개의 하위 호출이 생기는가? — 1개면 O(n) 또는 O(log n), 2개 이상이면 지수 가능성
4. 자료 구조를 새로 만드는가? — 만든다면 그 크기가 공간 복잡도
5. 정렬, 탐색 등 내장 함수를 쓰는가? — 내장 정렬은 보통 O(n log n), HashMap 조회는 평균 O(1)

마무리

복잡도	대표 패턴	n = 10^6일 때 체감
O(1)	인덱스 접근, 해시 조회	즉시
O(log n)	이진 탐색, 균형 트리	약 20회
O(n)	단순 순회, 선형 탐색	현실적
O(n log n)	효율적 정렬, 분할 정복	현실적
O(n²)	이중 반복, 단순 정렬	약 10¹² — 느림
O(2^n)	부분 집합, 메모이제이션 없는 재귀	사실상 불가능

1. Big-O는 "정확한 연산 횟수"가 아니라 "입력이 커질 때의 증가 등급" — 상수와 낮은 차수 항을 버려도 알고리즘 간 비교에는 충분합니다
2. 공간 복잡도는 "추가 메모리"만 센다 — 입력 자체가 아니라, 알고리즘이 동작하면서 할당하는 자료 구조와 콜 스택이 대상입니다
3. 시간과 공간은 트레이드오프 관계인 경우가 많다 — HashMap으로 시간을 줄이면 공간이 늘고, 정렬 후 순회하면 공간은 줄지만 시간이 더 듭니다
4. 복잡도 분석의 핵심은 "반복문 겹 수"와 "범위가 줄어드는 속도" — 이 두 가지를 먼저 보면 대부분의 코드에서 복잡도를 빠르게 잡을 수 있습니다