공간 복잡도

공간 복잡도는 입력 크기 n에 따라 알고리즘이 추가로 필요로 하는 메모리의 증가량을 점근적으로 나타낸 것이다. 일반적으로 공간 복잡도는 보조 공간(Auxiliary Space)을 의미하는데, 이는 입력 자체를 담아두는 메모리를 제외한 “알고리즘이 따로 쓰는 메모리” 를 의미한다. (총 공간 = 입력 공간 + 보조 공간)

 

최근에는 하드웨어의 발달로 인해 공간 복잡도의 중요성이 예전에 비해 많이 낮아졌다. 하지만 대규모 데이터 처리·클라우드 비용·컨테이너 메모리 제한이 있는 환경에서는 공간 복잡도가 여전히 중요한 설계 기준이다. 시간 복잡도와 공간 복잡도는 반비례적인 경향이 있지만 항상 반비례하는 것은 아니다.

 

이러한 공간 복잡도도 시간 복잡도와 마찬가지로 빅오 표기법을 사용한다.

 

---

공간 복잡도 계산법

 

1. 입력 크기 기호화

입력 값의 크기를 다음과 같이 기호로 정해둔다. n(배열 길이), m(다른 차원), V/E(그래프) 등.

문자열 2개라면 n = |A|, m = |B|

 

 

2. 추가 자료구조 나열

공간 복잡도는 결국 “무엇을 얼마나 더 만들었나”의 합이기 때문에 알고리즘이 “새로 만드는” 배열/맵/큐/스택의 크기가 얼마인지 알아야 한다.

new int[n] ⇒ O(n)
HashSet에 최대 k개 저장 ⇒ O(k) ≤ O(n).

 

 

3. 재귀 깊이 계산

알고리즘이 재귀 함수로 구현되어 있다면, 호출할 때마다 호출 스택(Call Stack)에 함수의 지역 변수·매개변수·리턴 주소 등이 쌓이게 된다. 따라서 재귀가 몇 단계까지 들어가는지(= 최대 호출 깊이)를 계산하는 것이 공간 복잡도에 큰 영향을 준다.

반대로 같은 로직이라도 재귀 대신 반복문으로 구현하면 호출 스택이 늘어나지 않으므로 그만큼 공간 복잡도가 줄어든다.

예시 1: 이진 탐색 (Binary Search)

탐색 구간을 절반씩 줄여가기 때문에 재귀 깊이는 log n

[재귀 구현] → 호출 스택 깊이 O(log n)
[반복문 구현] → 추가 스택 사용 없음 → O(1)

-----------------------------------------------------------------------------------

예시 2: 깊이 우선 탐색 (DFS)

DFS는 그래프/트리를 탐색할 때 자주 쓰이며, 재귀 깊이는 탐색 경로의 최대 길이와 같다.

[균형 잡힌 트리] 깊이가 대략 log n 수준 → 공간 복잡도 O(log n)
[편향된 구조 (한쪽으로만 뻗은 트리)] 깊이가 n까지 늘어남 → 공간 복잡도 O(n)

즉, DFS는 입력 구조에 따라 공간 복잡도가 달라지며, 최악의 경우 O(n)까지 올라간다.

 

 

4. 단계별 ‘피크(최대 동시 사용량)’만 합성

피크(peak - 최대 동시 사용량)는 공간 복잡도에서 특히 중요한 개념이다. 실행 중 어떤 구조들이 동시에 살아 있는지(참조 가능성)를 보고, 동시에 존재하지 않으면 max, 동시에 존재하면 합(+)으로 합성한다.

시간 복잡도는 한 단계의 시간이 지나가면 이미 소비된 것이므로 다음 단계와 그냥 더해 계산하고, 분기라면 실제로 실행될 더 오래 걸리는 쪽을 본다. 반면 공간 복잡도는 한 시점에 동시에 살아 있는 메모리만 신경 쓰기 때문에, 두 단계의 메모리가 겹치지 않으면 더 큰 쪽만 남기고, 겹치면 합쳐서 계산한다.

void f(int[] a) {
  byte[] buf = new byte[n]; // A: O(n) 메모리
  process(buf);             // buf 사용
  buf = null;               // 더 이상 참조 X (수거 가능)

  quicksortInPlace(a);      // B: 재귀 스택 O(log n)
}

 

 

5. 지배항만 남겨 표기

상수/하위 차수는 버리고 Big-O로 적는다.

O(n) + O(log n) ⇒ O(n), O(2n) ⇒ O(n)

 

---

공간 복잡도 예제

1) 최대값 찾기 — O(1)

int max(int[] a) {
    int ans = Integer.MIN_VALUE;   // 상수 개수 변수만 사용
    for (int v : a) ans = Math.max(ans, v);
    return ans;
}
// Space: O(1)

 

 

2) 이진 탐색 — 재귀 O(log n) vs 반복문 O(1)

int binSearchRec(int[] a, int l, int r, int x) {       // 재귀
    if (l > r) return -1;
    int m = l + (r - l) / 2;
    if (a[m] == x) return m;
    return (a[m] > x)
            ? binSearchRec(a, l, m - 1, x)
            : binSearchRec(a, m + 1, r, x);
}
// Space: O(log n)  (호출 스택 깊이)

int binSearchIter(int[] a, int x) {               // 반복문
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == x) return m;
        if (a[m] > x) r = m - 1;
        else          l = m + 1;
    }
    return -1;
}
// Space: O(1)

 

 

3) 중복 검사 — HashSet(O(n)) vs 값의 범위가 제한된 경우(O(1))

boolean hasDupSet(int[] a) {                 // 값의 범위에 제한 없음
    HashSet<Integer> seen = new HashSet<>();
    for (int x : a) if (!seen.add(x)) return true;
    return false;
}
// Space: O(n)  (배열에 어떤 값이든 들어올 수 있으므로, 최악의 경우 n개를 저장해야 함)

boolean hasDupLowercase(String s) {          // 각 문자가 'a'~'z'라는 제한
    boolean[] seen = new boolean[26];
    for (int i = 0; i < s.length(); i++) {
       int idx = s.charAt(i) - 'a';
       if (seen[idx]) return true;
       seen[idx] = true;
    }
    return false;
}
// Space: O(1)  (문자가 26개 중 하나라는 고정된 범위이므로, 문자열 길이가 커져도 배열 크기는 변하지 않음)

 

 

4) 합병정렬(Merge Sort) — O(n) (보조 배열)

void mergeSort(int[] a) {
    int[] buf = new int[a.length];   // 보조 배열 한 번만 생성
    sort(a, 0, a.length - 1, buf);
}

void sort(int[] a, int l, int r, int[] buf) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    sort(a, l, m, buf);
    sort(a, m + 1, r, buf);
    merge(a, l, m, r, buf);
}

void merge(int[] a, int l, int m, int r, int[] buf) {
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
       buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i <= m) buf[k++] = a[i++];
    while (j <= r) buf[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = buf[t];
}
// Space: O(n) (보조 배열) + O(log n) (재귀 스택) ⇒ 피크 O(n)

 

 

5) BFS (인접 리스트) — O(V)

int bfsCount(List<List<Integer>> g, int s) {
    int n = g.size();
    boolean[] visited = new boolean[n];                 // O(V)
    ArrayDeque<Integer> queue = new ArrayDeque<>(); // ≤ O(V)
    visited[s] = true; queue.add(s);
    int cnt = 0;
    while (!queue.isEmpty()) {
       int u = queue.removeFirst(); cnt++;
       for (int v : g.get(u)) if (!visited[v]) { visited[v] = true; queue.add(v); }
    }
    return cnt;
}
// Space: O(V)  (visited O(V) + queue 최악 O(V))

---

출처 : https://adjh54.tistory.com/186 https://www.youtube.com/watch?v=LBR9K8NPtvQ https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84 https://coding-factory.tistory.com/609

---