참고 : 공간 복잡도
왜 알아야 할까?
실제 알고리즘 구현시에는, 기능 작동도 물론 중요하지만 얼마나 효율적인지도 그만큼 중요하다. 요즘같은 대용량 시스템 같은경우에는 공간 복잡도 보다는 시간 복잡도가 우선으로 생각되겠다.
저번 프로젝트에서처럼 많은 서버로의 req 와 res 가 발생하고, forEach, map 같은 무거운 순회함수가 실행되는 경우 모든 프로세스를 마칠 수 없을 뿐만 아니라 많은 스택메모리를 차지하여 안좋은 사용자경험을 느끼게 할 수 있다.
따라서 계산복잡도를 고려하는 것이 성능향상 및 좋은 코드를 짜는데 도움이 될 수 있을 것이다.
알고리즘 계산 복잡도는 다음 두가지 척도로 표현될 수 있음
- 시간 복잡도 : 얼마나 빠르게 실행되는지
- 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지
통상적으로 둘 다를 만족시키기는 어려움
- 시간과 공간은 반비례적 경향이 있음
공간 복잡도 대략적인 계산은 필요함
- 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음
- 그래서 기존 알고리즘 문제에 시간 복잡도 뿐만 아니라, 공간 복잡도 제약사항이 있는 경우가 있음
Complexity
- expected worst-case time complexity: O(N)
- expected worst-case space complexity: O(N)
현업에서 최근 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있음
1. 공간 복잡도 (Space Complexity)
- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함.
- 총 필요 저장 공간
- 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
- 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
- S( P ) = c + S~p~(n)
- c: 고정 공간
- S~p~(n): 가변 공간
빅 오 표기법을 생각해 볼 때, 고정공간은 상수이므로 공간 복잡도는 가변 공간에 좌우 됨
공간 복잡도 예제1
- n! 팩토리얼 구하기
- n! = 1 x 2 x … x n
- n의 값에 상관없이 변수 n, 변수 fac, 변수 index 만 필요함
- 공간 복잡도는 O(1)
1
2
3
4
5
6
7
def factorial(n):
fac = 1
for index in range(2, n+1):
fac = fac * index
return fac
factorial(3) ## 6
공간 복잡도 예제2
- n! 팩토리얼 구하기
- n! = 1 x 2 x … x n
- 재귀함수를 사용하였으므로, n에따라 변수 n이 n개가 만들어지게 됨
- factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1 까지 스택에 쌓이게 됨
- 공간 복잡도는 O(n)
1
2
3
4
5
def fatorial(n):
if n > 1:
return n * factorial (n-1)
else:
return 1