공간 복잡도

요약

• 알고리즘이 수행되는 동안 사용하는 메모리의 양을 나타내는 척도로 빅오 표기법, Bing-O Notation을 사용한다.

내용

특징

• 알고리즘이 수행되는 동안 사용하는 메모리의 양을 나타내는 척도이다.
• 알고리즘의 입력 크기(n)에 따라서 얼마나 많은 메모리가 필요한지 분석하여, 메모리 효율성을 평가할 수 있다.

구성 요소

• 고정 공간(Fixed Space)
  • 알고리즘이 실행되면서 입력 크기와 상관 없이 일정하게 사용하는 공간이다.
  • 상수의 변수, 고정 크기의 배열, 상수 크기의 객체 등이 해당한다.
  • 입력 크기에 관계 없이 동일한 크기를 차지하기 때문에 공간 복잡도에 큰 영향을 주지 않는다.
• 가변 공간(Variable Space)
  • 알고리즘이 실행될 때 입력 크기에 따라 달리지는 공간
  • 동적 배열이나 재귀 호출에서 사용하는 메모리 등이 해당한다.
  • 입력 크기(n)에 따라 가변적으로 변동하는 메모리이기 때문에, 주로 가변 공간이 공간 복잡도에 큰 영향을 미친다.

계산 방법

1. O(1)
   • 알고리즘의 메모리 사용량이 입력 크기와 관계없이 일정한 경우
   • 다음 함수는 입력 크기 n과 관계 없이 count 변수 하나만 사용하므로 공간 복잡도는 O(1)이다.

func constantSpace(n int) int {
    count := 0 // O(1) 공간
    for i := 0; i < n; i++ {
        count += i
    }
    return count
}

2. O(n)
   • 알고리즘이 입력 크기에 비례하여 메모리를 사용하는 경우
   • 다음 함수는 크기 n의 배열 arr를 생성하므로 공간 복잡도는 O(n)이다.

func linearSpace(n int) []int {
    arr := make([]int, n) // O(n) 공간
    for i := 0; i < n; i++ {
        arr[i] = i
    }
    return arr
}

3. O(n^2)
   • 입력 크기에 비례하여 이차적으로 공간을 사용하는 경우
   • 위 함수는 n*n크기의 이차원 배열을 생성하므로 공간 복잡도는 O(n^2)이다.

func quadraticSpace(n int) [][]int {
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n) // O(n^2) 공간
    }
    return matrix
}

4. O(n)
   • 재귀 호출에서는 함수 호출이 쌓이면서 콜 스택을 차지하기 때문에, 재귀 깊이에 따라 추가 메모리가 필요하게 된다.

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

참고