시간복잡도와 공간복잡도

공간복잡도란?

: 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계, 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것
(저장하는 데이터의 양이 1개의 공간을 사용)

시간복잡도란?

: 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계, 예를 들어 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 관계
(함수의 실행시간을 점근적 분석을 통해서 점근적 표기법으로 표현한 것)

점근적 표기법

: 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법

• 빅오(Big-O)표기법: 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기
• 빅 오메가(Big-Ω)표기법: 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대한 표기

최악의 경우를 대비하기 위해 거의 모든 알고리즘을 빅오 표기법으로 분석함

시간 복잡도를 이용하여 알고리즘의 성능을 분석하면, 알고리즘의 실행 시간이 입력 크기에 어떻게 의존하는지를 파악할 수 있습니다. 그 결과로 더 나은 알고리즘을 선택하거나 알고리즘을 개선하여 실행 시간을 줄일 수 있습니다.