메모리 복잡도(Memory Complexity)

메모리 복잡도는 알고리즘이 문제를 해결하기 위해 얼마나 많은 메모리 공간을 필요로 하는지를 나타내는 척도이다. 시간 복잡도와 마찬가지로, 메모리 복잡도 또한 빅오 표기법(Big-O notation)을 사용하여 나타낸다.

---

1. 메모리 복잡도의 정의

알고리즘의 메모리 복잡도는 입력 크기 $n$에 따라 알고리즘 실행 중 필요로 하는 메모리 공간을 의미한다. 주로 사용하는 데이터 구조의 크기나, 함수 호출 시 생성되는 콜 스택(call stack)의 크기 등을 포함한다.

메모리 복잡도는 일반적으로 다음과 같은 형태로 나타낸다.

여기서 $f(n)$은 입력 크기 $n$에 따라 변하는 메모리의 양을 의미한다.

---

2. 메모리 복잡도에 영향을 주는 요소

알고리즘의 메모리 복잡도에 영향을 주는 주요 요소는 다음과 같다.

• 입력 데이터 크기
• 사용되는 데이터 구조(배열, 리스트, 큐, 스택, 트리 등)
• 재귀 호출 시의 스택 깊이(call stack depth)
• 동적 할당되는 메모리의 양

---

3. 메모리 복잡도의 예시

다음은 대표적인 메모리 복잡도 예시이다.

메모리 복잡도	설명	예시
$O(1)$	입력 크기와 상관없이 일정한 메모리를 사용한다.	변수 할당, 단순 반복문
$O(n)$	입력 크기 $n$에 비례하여 메모리를 사용한다.	길이 $n$인 배열을 사용하는 경우
$O(n^2)$	입력 크기의 제곱에 비례하여 메모리를 사용한다.	$n \times n$ 행렬 사용
$O(\log n)$	입력 크기의 로그에 비례하여 메모리를 사용한다.	이진 탐색, 재귀 호출 깊이가 $\log n$인 경우

---

4. 메모리 복잡도의 예시 코드

아래는 대표적인 메모리 복잡도 예시 코드이다.

(1) $O(1)$ - 상수 공간

def constant_memory(n):
    result = 0
    for i in range(n):
        result += i
    return result

입력 크기와 관계없이 일정한 개수의 변수만 사용한다.

---

(2) $O(n)$ - 선형 공간

def linear_memory(n):
    arr = [0] * n
    for i in range(n):
        arr[i] = i
    return arr

입력 크기 $n$에 비례하는 배열을 사용하여 메모리 공간이 증가한다.

---

(3) $O(n^2)$ - 이차 공간

def quadratic_memory(n):
    matrix = [[0 for _ in range(n)] for _ in range(n)]
    return matrix

$n \times n$ 크기의 행렬을 사용하므로 메모리 공간은 $n^2$에 비례한다.

---

(4) 재귀 호출과 메모리 복잡도

재귀(recursive) 호출은 호출될 때마다 추가적인 메모리를 사용하여 콜 스택에 데이터를 쌓기 때문에 메모리 복잡도에 영향을 준다.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

이 재귀 함수는 $n$번의 호출이 이루어지므로 콜 스택 깊이가 $O(n)$이다.

---

5. 재귀 vs 비재귀 메모리 복잡도 차이의 이유

일반적으로 재귀 방식이 비재귀(반복문) 방식보다 메모리를 더 많이 사용하는 이유는, 재귀 함수가 호출될 때마다 콜 스택(call stack)에 함수 호출 상태를 저장하기 때문이다.

반면, 반복문으로 구현된 알고리즘은 한 번의 함수 호출 내에서 일정한 공간만을 사용하기 때문에 재귀 방식에 비해 상대적으로 메모리 사용량이 적어진다.

단, 재귀 호출이 꼬리 재귀(tail recursion) 형태로 구현되면, 컴파일러 최적화를 통해 반복문과 비슷한 수준의 메모리 사용량을 가질 수 있다. 하지만 대부분의 언어(파이썬 포함)는 이 최적화를 기본적으로 제공하지 않는다.

---

6. 메모리 복잡도 최적화 방법

알고리즘의 메모리 복잡도를 낮추는 대표적인 방법은 다음과 같다.

• 불필요한 데이터 구조나 배열 사용 최소화
• 반복문을 사용하여 재귀 호출을 대체
• 알고리즘 설계 시 공간 효율적인 자료 구조 사용(예: 연결 리스트 대신 배열 사용)

---

7. 결론 및 중요성

메모리 복잡도는 알고리즘 설계 시 효율성과 성능 최적화 측면에서 중요한 고려 요소이다. 특히 제한된 메모리 환경에서 실행되는 시스템(임베디드 시스템, 모바일 앱 등)에서는 메모리 복잡도 최적화가 필수적이다. 따라서 알고리즘 설계 시 메모리 사용량을 면밀히 분석하여 적절한 자료구조와 방식을 선택하는 것이 중요하다.