공간복잡도 ..?

공간복잡도 → 얼마나 많은 저장 공간이 필요할까 ?

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓴다.

• 시간 복잡도와 공간 복잡도를 둘다 적게 가져가기는 어렵다.
  • 시간과 공간은 반비례적 경향이 있다.
  • 최근 대용량 시스템이 보편화 되면서, 공간 복잡도 보다는 시간 복잡도가 우선이 되었다.

공간 복잡도의 계산

• 기존에는 공간 복잡도도 고려해야 하는 경우도 있었다.
• 기존 알고리즘 문제들은 공간 복잡도 제약 사항이 있는 경우가 있다.
• 기존 문제들에 영향을 받아 면접시에도 공간 복잡도를 묻는 경우가 있다.
  • 현업에서는 최근 빅데이터를 다룰 때 저장 공간을 고려해서 구현을 하는 경우도 있다.
  • 그 외의 경우라면 보통은 시간복잡도만 생각을 한다.
• 공간 복잡도란?
  • 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다.
  • 총 필요 저장 공간
    • 고정 공간 ⇒ 코드 저장 공간, (알고리즘과 무관한 공간)
    • 가변 공간 ⇒ 실행 중 동적으로 필요한 공간 (알고리즘 실행과 관련있는 공간)
  • 빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.
  • 메소드를 호출할때의 예제
    • 매개 변수로 어떠한 값을 리턴해줄때, 매개변수의 값에 상관없이 고정된 코드 저장 공간이 존재할때 ⇒ O(1)
    • 매개 변수의 값에 따라서 메모리에 차지하는 공간이 많아진다 → 가변 공간 ⇒ O(n)

마무리

• 공간복잡도에 대해서 짧게 정리해보았습니다.
• 단순히 메모리를 얼마나 잡아먹느냐가 관건인것같습니다.
• 제대로 정리가 된 기분은 아니지만 그래도 강의를 들었으니 코딩을 하다가 깨닫게 되는 날이 올거라 생각이 듭니다.