알고리즘 공간복잡도

안녕하세요 :)
오랜만에 블로그 포스팅을 해보려 합니다.
그동안 포스팅을 하지 않은 구질구질한 이유는?
사실 요 몇 주 롤체토스에 빠졌다가 실버4 찍고 관뒀습니다.

 

무튼... 오늘 공부해 볼 주제는 공간복잡도(space complexity) 입니다.

 

공간복잡도란?
프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양입니다.
공간복잡도는 총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있고
수식으로는 S(P) = c + Sp(n)으로 표기합니다.

 

공간복잡도는 어떻게 표기하느냐?
공간복잡도는 Big-O표기법을 사용합니다.
시간복잡도를 표현할 때도 Big-O 사용했었죠?
Big-O는 알고리즘의 성능을 수학적으로 표현해주는 표기법이기 때문에
시간복잡도 공간복잡도 모두 Big-O 표기법을 사용합니다.

 

공간복잡도 계산법
1차원 배열을 만든다고 가정해봅시다.
그럼 우리는 O(n)의 공간이 필요합니다.

2차원 배열을 만든다고 가정해봅시다.
그럼 우리는 O(n^2)의 공간이 필요합니다.

여기까지 오케이

다음과 같은 코드는 공간복잡도가 어떻게 될까요?

func sum(n: Int) -> Int {
    if n <= 0 {
        return 0
    } else {
        return sum(n: n - 1)
    }
}

O(n)시간복잡도와 O(n)공간복잡도를 가집니다.

재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함되기 때문입니다.
3을 넣었다고 가정하고 흐름을 살펴봅시다.

호출될 때마다 스택의 깊이(depth)가 깊어지는 것을 확인할 수 있습니다.
ㅇㅇ재귀 호출은 전부 호출 스택에 더해지고 실제 메모리 공간을 잡아먹습니다.

 

그럼 0과 n사이에서 인접한 두 원소의 합을 구하는 아래 함수는 공간복잡도가 어떻게 될까요?

func add(a: Int, b: Int) -> Int {
    return a + b
}

func pairSum(n: Int) -> Int {
    var sum = 0
    
    for i in 0..<n {
        sum = sum + add(a: i, b: i + 1)
    }
    
    return sum
}

n까지 돌면서 add를 호출하네?
공간복잡도O(n)인가? 아닙니다!

n번 호출했다고 해서 O(n)의 공간을 사용하는 건 아닙니다.
이 함수들이 호출 스택에 동시에 존재하지 않기 때문입니다.
 
함수를 대략 O(n)번 호출했지만, 이 함수들이 호출 스택에 동시에 존재하지는 않으므로 
O(1)의 공간복잡도를 가집니다.

---

지금까지 시간복잡도는 개선하려 노력했는데, 공간복잡도는 개선하려 노력하지 않았나요?
시간뿐 아니라 메모리(공간)도 신경 써야 합니다!
(나한테 하는 소리임)

---

resource:
cracking the coding interview
https://en.wikipedia.org/wiki/Space_complexity