•
알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
◦
시간 복잡도: 얼마나 빠르게 실행되는지
◦
공간 복잡도: 얼마나 많은 저장 공간이 필요한지
⇒ 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘
•
통상적으로 둘 다를 만족시키기는 어려움
◦
시간과 공간은 반비례적 경향이 있음
◦
최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
◦
그래서! 알고리즘은 시간 복잡도가 중심
공간 복잡도 대략적인 계산은 필요하다.
•
기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음
•
그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음
•
또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 공간 복잡도를 묻는 경우도 있음
Complexity
•
expected worst-case time complexity: O(N)
•
expected worst-case space complexity: O(N)
⇒ 현업에서 최근 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있음
공간 복잡도 (Space Complexity)
•
프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
•
총 필요 저장 공간
◦
고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
◦
가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
◦
▪
: 고정 공간
▪
: 가변 공간
⇒ 빅오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.
