알고리즘을 이론적으로 분석할 때는 일반적으로 점근적(asymptotic) 관점에서 복잡도를 추정합니다. 즉, 임의로 큰 입력값에 대해서도 성립하도록 복잡도 함수를 평가하는 방식입니다. 참고로 '알고리즘 분석(Analysis of Algorithms)'이라는 용어는 컴퓨터 과학의 거장 도널드 커누스(Donald Knuth)가 처음 사용한 것으로 유명합니다.
알고리즘 분석은 계산 복잡도 이론(Computational Complexity Theory)의 핵심적인 부분입니다. 이 이론은 특정 계산 문제를 해결하기 위해 알고리즘이 필요로 하는 자원의 양을 이론적으로 추정해 줍니다. 대부분의 알고리즘은 길이에 제한 없는 임의의 입력을 처리하도록 설계되므로, 알고리즘 분석이란 곧 해당 알고리즘을 실행하는 데 소요되는 시간과 공간(메모리) 자원의 양을 결정하는 작업이라 할 수 있습니다.
통상적으로 알고리즘의 효율성 또는 실행 시간은 입력 크기와 실행 단계 수 사이의 관계를 나타내는 함수로 표현됩니다. 이를 시간 복잡도(Time Complexity)라고 하며, 같은 방식으로 메모리 사용량과 입력 크기의 관계를 나타낸 것을 공간 복잡도(Space Complexity)라고 부릅니다.
이 섹션에서 다룰 주제
- 알고리즘과 복잡도(Complexities)의 개념
- 점근적 분석(Asymptotic Analysis)
- 점근적 표기법(Asymptotic Notations)
- 분할 상환 분석(Amortized Analysis)
- 공간 복잡도(Space Complexity)
- 의사 다항식(Pseudo Polynomial) 유형 알고리즘과 PATS(의사 다항식 근사 기법)