📌 시간 복잡도와 공간 복잡도

• 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
  1. 시간 복잡도 : 얼마나 빠르게 실행되는지
  2. 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지

✨ 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘 ✨

• 그러나 일반적으로는 둘 다 만족 시키기는 어려움
• 시간 복잡도, 공간 복잡도는 반비례적으로 상호작용하는 경향이 있음
• 최근에는 대용량 시스템이 보편화 되면서 공간 복잡도 < 시간 복잡도
• 따라서 알고리즘은 기본적으로 시간 복잡도가 중심이 됨

---

📌 공간 복잡도란?

• 공간 복잡도 : 프로그램을 실행 및 완료하는데 필요한 저장공간의 양
• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간

$S(P) = c + S_p(n)$

• $c$ : 고정 공간
• $S_p(n)$ : 가변 공간

• 공간 복잡도는 가변 공간에 따라 좌우된다! (왜냐하면 $c$는 상수이므로 빅 오 표기법에 영향을 미치지 않음)

---

📌 공간 복잡도 예제로 알아보기

• 문제 : $n!$ 팩토리얼 구하기
• $n! : 1 × 2 × ... × n$

💡 방법 1

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

• 공간 복잡도는 $O(1)$
• n의 값에 상관 없이 변수 공간이 n, fac, index에 대해서만 필요함

💡 방법 2

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

• 공간 복잡도는 $O(n)$
• 재귀 함수를 사용하여 n에 따라 재귀 함수가 호출될 때마다 변수 n이 만들어짐
• 따라서 최종적으로 변수 n이 n개 만들어짐