테마
시간 복잡도와 공간 복잡도 2
시간 복잡도와 공간 복잡도에서 본 빅오 표기법(Big-O notation)으로 실제 비용을 말할 때 함께 따져야 할 관점을 이어서 다룬다. 같은 알고리즘도 어떤 입력을 가정하느냐에 따라 최선·평균·최악이 갈리고, 가끔 비싼 연산이 섞이면 분할 상환 분석(amortized analysis)으로 한 번당 비용을 본다. 마지막으로 알고리즘이 추가로 쓰는 메모리를 세는 공간 복잡도(space complexity)를 정리한다.
최선·평균·최악
같은 알고리즘도 입력에 따라 비용이 다르다. 정렬되지 않은 배열(array)에서 값을 앞에서부터 찾는 선형 탐색(linear search)을 예로 들면, 찾는 값이 첫 칸이면 1번에 끝나고(최선), 마지막 칸이거나 없으면 n번 본다(최악). 평균은 약 n/2번이고, 상수 1/2을 버리면 O(n)이다.
면접이나 문서에서 복잡도를 말할 때는 보통 최악을 기준으로 한다. 최악은 "아무리 운이 나빠도 이보다는 느리지 않다"는 보장이 되기 때문이다. 다만 평균이 실제 성능을 더 잘 설명하는 경우도 있다. 해시 테이블(hash table)은 평균 O(1)이지만 최악 O(n)이고, 퀵 정렬(quicksort)은 평균 O(n log n)이지만 최악 O(n²)이다. n log n은 n보다 조금 큰 정도지만, n²은 입력이 10배 늘면 비용이 100배로 는다. 빅오 표기법(상한을 적는 방법)과 최선·평균·최악(어떤 입력을 가정하는가)은 서로 다른 축이라는 점을 구분해 둔다.
분할 상환 분석: 가끔 비싼 연산
동적 배열(dynamic array)은 칸이 모자라면 더 큰 배열을 새로 잡고 기존 원소를 전부 옮겨 담으며 자라는 배열이다. 옮기는 순간의 추가(append)는 원소 수만큼 걸리는 O(n)이다. 그렇다고 추가가 O(n)이라고 말하면 실제보다 훨씬 비싸게 평가하게 된다.
분할 상환 분석(amortized analysis)은 이런 경우 연산 여러 번의 전체 비용을 횟수로 나눠 한 번당 비용을 본다. 교과서에서 흔히 쓰는 "가득 차면 용량을 두 배로" 모델에서, 원소 n개를 넣는 동안 옮기는 횟수는 1 + 2 + 4 + … + n이다. 두 배씩 커지는 수는 다 더해도 마지막 값의 두 배를 넘지 않으므로 2n보다 작다. 원소를 넣는 n번까지 더해도 전체가 O(n)이므로 한 번당 분할 상환 O(1)이다. 두 배가 아니어도 1보다 큰 일정 비율로 키우면 옮기는 횟수의 합이 여전히 n의 상수배로 묶이므로 결과는 같다. 반대로 한 칸씩 늘리면 매번 옮겨야 해서 한 번당 O(n)이 된다. Java ArrayList 문서도 추가가 "분할 상환 상수 시간(amortized constant time)"이라고만 약속한다1.
공간 복잡도
공간 복잡도는 보통 입력을 담는 메모리를 빼고, 알고리즘이 추가로 쓰는 메모리를 센다. 배열을 제자리(in-place)에서, 즉 새 배열 없이 원래 배열 안에서 뒤집으면 변수 몇 개만 쓰므로 O(1)이고, 결과를 새 배열에 담으면 O(n)이다.
재귀(recursion)는 함수가 자기 자신을 다시 호출해 문제를 작게 나눠 푸는 방식이다. 재귀는 겉보기엔 변수를 안 만들어도 메모리를 쓴다. 함수를 호출할 때마다 지역 변수와 돌아갈 위치가 호출 스택(call stack)에 한 겹씩 쌓이기 때문이다. 그래서 재귀 깊이가 n이면 공간도 O(n)이고, 깊이가 너무 깊으면 호출 스택이 정해진 크기를 넘쳐 프로그램이 죽는 스택 오버플로(stack overflow)가 난다.
java
int sum(int n) { return n == 0 ? 0 : n + sum(n - 1); } // 호출이 n겹 쌓임 → 공간 O(n)
int sumLoop(int n) { int s = 0; for (int i = 1; i <= n; i++) s += i; return s; } // 공간 O(1)시간과 공간은 자주 맞바꾼다. 앞 문서에서 모든 쌍을 비교해 O(n²)이던 중복 찾기를 바꿔 보자. 원소를 하나씩 보면서 이미 본 값인지 해시 테이블에서 확인하고, 없으면 넣는다. 그러면 시간은 평균 O(n)으로 줄지만, 해시 테이블에 값을 담느라 공간이 O(n) 더 든다. 메모리가 넉넉하면 공간을 써서 시간을 사는 것이 흔한 선택이다.
면접 포인트
- "복잡도는 최선·평균·최악 중 무엇으로 말하나요?" → 보통 최악. "이보다 느리지 않다"는 보장이 되기 때문. 해시 테이블·퀵 정렬처럼 평균과 최악이 크게 다르면 둘 다 말한다.
- 빅오 표기법을 "최악"과 같은 뜻으로 말하면 틀린다. 빅오 표기법은 상한을 적는 방법이고, 최악·평균은 어떤 입력을 가정하느냐다.
- "동적 배열의 추가는 O(1)인가요?" → 분할 상환 O(1). 확장 순간은 O(n)이지만 용량을 일정 비율로 키우면 평균이 상수.
- "재귀의 공간 복잡도는?" → 호출 스택 깊이만큼. 깊이 n이면 O(n).
참고
늘리는 비율은 API 문서가 정하지 않는다. OpenJDK 구현은 가득 차면 기존 용량의 약 1.5배로 늘린다(
oldCapacity >> 1만큼 추가). ↩︎