[Algorithm] 시간복잡도와 공간복잡도

정의

• 시간복잡도 : 알고리즘의 수행시간 분석 결과 - 얼마나 빠르게 실행되는가
• 공간복잡도 : 알고리즘의 메모리 사용량에 대한 분석 결과 - 얼마나 많은 자원이 요구되는가

효율적인 알고리즘 : 알고리즘이 수행을 시작하여 결과가 도출될 때까지 걸리는 시간이 짧고 연산하는 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 알고리즘

시간복잡도

알고리즘을 수행하는데 연산(산술, 대입, 비교, 이동) 들이 몇 번 이루어지는지를 숫자로 표기함
동일한 알고리즘도 입력되는 데이터에 따라 실행시간이 다르며 최선, 평균, 최악의 경우로 나누어질 수 있다

ex) 여러 정렬들의 시간복잡도

빅오표기법

시간복잡도 함수에서 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 할 목적으로 시간복잡도를 표기하는 방법

ex) O(n), O(nlogn)

공간복잡도

프로그램을 실행시킨 후 완료하는데 필요로하는 자원 공간의 양

총 공간요구 = 고정 공간요구 + 가변 공간요구

고정공간 : 알고리즘의 특성과는 무관한 부분으로 코드를 저장하기위한 공간, 프로그램 수행을 위해 시스템이 필요로 하는 공간 등이 이에 포함된다

가변공간 : 알고리즘의 특성과 밀접한 부분으로 문제를 해결하기 위해 동적으로필요로하는 공간을 의미한다. 변수를 저장하기 위한 공간, 순환호출 시 요구되는 추가공간 등이 이에 포함된다