공간 복잡도

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

 

좋은 프로그램은 실행 시간도 짧고, 저장 공간도 적게 쓰는 프로그램 (=알고리즘)

• 통상 둘 다를 만족시키기는 어려움
  • 시간과 공간은 반비례적 경향이 있음
  • 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
  • 그래서! 알고리즘은 시간 복잡도가 중심
  • 하지만, 공간 복잡도는 기본이기 때문에 기본이 안되서 떨어지는 경우도 많습니다!

 

• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
  • S(P) = c + Sp(n)
    • c: 고정 공간
    • 𝑆𝑝(𝑛)Sp(n): 가변 공간
• 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우됩니다.

공간 복잡도와 시간 복잡도 모두 빅 오 표기법으로 표현한다. = O(n)

 

컴퓨터 과학에서 O(logN)은 O(log₂N)을 줄여 부르는 말이다.

데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘