240314 TIL - 공간복잡도와 자료구조에서의 시간 복잡도

오늘은 알고리즘에서 많이 보았던 복잡도에 대한 부분을 공부하고 정리해 보았다.

공간복잡도?

• 공간 복잡도는 프로그램(알고리즘)을 실행시켰을 때 필요로 하는 자원의 공간의 양
• 시간복잡도와 함께 알고리즘의 효율성을 평가하는 주요 기준 중 하나
• 공간복잡도 = 고정 공간 요구량 + 가변 공간 요구량
  • 고정 공간: 입력과 출력의 크기에 관계없이 고정된 저장 공간(코드 저장 공간, 단순 변수 등)
  • 가변 공간: 실행 중 동적으로 할당되는 공간(동적 배열, 재귀 호출 등)
• 공간 복잡도의 최적화
  • 최적화의 이유
    • 메모리 자원은 한정적, 효율적인 메모리 사용은 프로그램의 성능을 크게 향상시킴 특히, 대규모 데이터를 다루는 애플리케이션에서 공간복잡도의 최적화는 필수적
  • 최적화 방법
  • 불필요한 변수, 자료구조의 사용을 최소화
  • 재귀 대신 반복문을 사용하여 스택 오버플로우의 위험을 줄인다
  • 데이터 압축, 메모리 풀링 등의 기법을 활용하여 메모리 사용을 최적화
  • 메모리 풀링
    자료 구조에서의 시간 복잡도

이렇게 공간복잡도에 대한 공간복잡도를 최적화하는데 사용하는 메모리 풀링, 그리고 자료구조에서의 평균, 최악의 시간복잡도까지 알아보았다. 알고리즘 문제를 풀 때마다 공간복잡도는 신경쓰지 않고 시간에만 조금 신경을 썼는데 오늘 배운 내용을 바탕으로 공간복잡도에 대해서도 약간은 신경을 쓰고 자료구조별 시간복잡도도 신경을써서 최적의 자료구조를 선택할 수 있도록 노력해야겠다.