[알고리즘 이론] 공간 복잡도 (Space Complexity)

• 공간 복잡도 : 프로그램을 실행 및 완료하는데 필요한 저장 공간의 양

 

 

(참고)

• 알고리즘 계산 복잡도 척도
  • 시간 복잡도 : 속도 (얼마나 빨리 실행되는가)
  • 공간 복잡도 : 저장 공간 (얼마나 많은 저장 공간이 필요한가)
  • 둘 다 만족하면 좋지만, 시간과 공간은 반비례적인 경향이 있음
  • 대용량 시스템의 보편화로 인해, 시간 복잡도의 우선순위 >> 공간 복잡도의 우선순위

 

 

예시) 공간 복잡도 예제 1

""" n! 팩토리얼 구하기 """

# n의 값에 상관없이 변수 n, fac, index만 필요
# 공간 복잡도 = O(1)

def factorial(n):
	fac = 1
	for index in range(2, n+1):
		fac = fac * index
	return fac

fac(3) # 결과: 6

 

예시) 공간 복잡도 예제 2

""" n! 팩토리얼 구하기 """

# 재귀함수 사용
# n에 따라 변수 n이 n개 만들어짐
# 공간 복잡도 = O(n)

def factorial(n):
	if n > 1 :
		return n * factorial(n-1)
	else:
		return 1