공간복잡도

#it #알고리즘 #자료구조 #공간복잡도 #bigo

기본 정보

명칭: 공간 복잡도
영문명: Space Complexity
분류: 알고리즘 분석
주요 용도: 프로그램의 메모리 사용량 분석
관련 주제: #공간복잡도 #알고리즘 #자료구조 #BigO

개요

공간 복잡도(Space Complexity)는

알고리즘이 실행되는 동안 사용하는 메모리의 양

을 의미한다.

보통 시간 복잡도(Time Complexity)와 함께 알고리즘의 성능을 평가할 때 사용한다.

공간 복잡도 구조

프로그램 실행

↓

변수 생성

↓

배열 생성

↓

재귀 호출

↓

메모리 사용

↓

공간 복잡도 계산

공간 복잡도 구성

공간 복잡도는 크게 두 부분으로 나뉜다.

총 공간 복잡도

=

고정 공간

+

가변 공간

고정 공간 (Fixed Space)

프로그램 실행 시 항상 필요한 메모리

예시

int a;
int b;

가변 공간 (Variable Space)

입력 크기에 따라 증가하는 메모리

예시

int arr[n];

Big-O 표기법

공간 복잡도 역시 Big-O로 표현한다.

공간 복잡도	의미
O(1)	상수 공간
O(log n)	로그 공간
O(n)	선형 공간
O(n log n)	로그 선형 공간
O(n²)	제곱 공간

O(1)

상수 공간

입력 크기와 관계없이 메모리가 일정하다.

def sum_two(a, b):
    result = a + b
    return result

사용 메모리

a
b
result

고정

O(1)

O(n)

선형 공간

입력 크기만큼 메모리가 증가한다.

def create_list(n):
    arr = []

    for i in range(n):
        arr.append(i)

    return arr

메모리 사용

n=10

10개 저장

n=100

100개 저장

따라서

O(n)

O(n²)

제곱 공간

2차원 배열 생성

def matrix(n):

    arr = [

        [0] * n

        for _ in range(n)

    ]

    return arr

사용 공간

n × n

즉

O(n²)

재귀와 공간 복잡도

재귀 함수는 호출 스택을 사용한다.

def factorial(n):

    if n == 0:
        return 1

    return n * factorial(n - 1)

호출 스택

factorial(5)

↓

factorial(4)

↓

factorial(3)

↓

factorial(2)

↓

factorial(1)

메모리 사용량

O(n)

반복문 vs 재귀

반복문

def loop(n):

    for i in range(n):
        pass

O(1)

재귀

def recursive(n):

    if n == 0:
        return

    recursive(n - 1)

O(n)

호출 스택이 쌓인다.

시간 복잡도와 차이

시간 복잡도

얼마나 오래 걸리는가

공간 복잡도

얼마나 많은 메모리를 사용하는가

예시

for i in range(n):
    print(i)

시간

O(n)

공간

O(1)

배열과 연결 리스트

배열

데이터 저장

↓

O(n)

연결 리스트

데이터

+

포인터 저장

↓

더 많은 메모리 사용

DFS와 BFS

DFS

재귀 사용

↓

호출 스택

↓

O(h)

BFS

큐 사용

↓

최악 O(n)

대표 예제

배열 복사

def copy_array(arr):

    return arr[:]

새 배열 생성

O(n)

배열 뒤집기

arr.reverse()

추가 배열 없음

O(1)

실무 예시

PHP

$list = [];

foreach ($rows as $row) {

    $list[] = $row;

}

전체 데이터를 메모리에 올림

O(n)

MySQL 페이징

LIMIT 20

메모리 절약

Pandas

df = pd.read_csv(
    "big.csv"
)

파일 전체 로딩

O(n)

공간 최적화 방법

불필요한 배열 제거

# 나쁜 예
new_arr = arr.copy()

# 좋은 예
arr.sort()

재귀 대신 반복문

재귀

↓

반복문

Generator 사용

yield

필요한 만큼만 메모리 사용

Streaming 처리

한 줄씩 읽기

대용량 파일 처리 시 유용

실무 메모

실무에서는 다음과 같은 방식이 권장된다.

대용량 데이터는 한 번에 메모리에 올리지 않기
배열 복사 최소화
재귀 깊이 주의
Generator 적극 활용
캐시 사용 시 메모리 증가 고려
BFS는 메모리 사용량 확인
Pandas 사용 시 메모리 프로파일링
API 응답은 필요한 데이터만 반환
LIMIT 사용 습관화
시간 복잡도와 공간 복잡도를 함께 고려

면접 단골 질문

Q1

배열 100만 개를 복사하면 공간 복잡도는?

O(n)

Q2

재귀 팩토리얼 공간 복잡도는?

O(n)

Q3

반복문 팩토리얼 공간 복잡도는?

O(1)

함께 사용하는 개념

출처

Introduction to Algorithms (CLRS)
GeeksforGeeks
Wikipedia - Space Complexity

메모

코딩테스트에서는 시간 복잡도보다 공간 복잡도를 놓치는 경우가 많음
DFS 재귀 깊이 초과 문제 자주 출제
TreeView CMS에서는 SQL 최적화보다 PHP 배열 메모리 사용량이 병목이 될 수 있음
Pandas, AI, 로그 분석 시 공간 복잡도 중요