프로그램의 규모가 커지고 처리해야 하는 데이터의 양이 많아지면서 알고리즘 효율성에 대한 분석이 필요하게 되었다. 알고리즘이 수행을 시작하여 결과를 도출할때 까지 걸리는 시간이 적고 사용하는 컴퓨터 메모리가 작으면 효율적인 알고리즘이라 할 수 있다. 이를 평가하는데는 계산 복잡도 지표를 사용한다.
계산 복잡도 (Computational Complexity) 개념
계산 복잡도 이론이란 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다.
복잡도의 기준은 알고리즘이 소모하는 자원에 따라 두 가지로 분류할 수 있다.
->시간 복잡도: 알고리즘이 소요하는 시간
->공간 복잡도: 알고리즘의 메모리 사용량
시간 복잡도는 “얼마나 빠르게 실행되느냐” 그리고 공간 복잡도는 “얼마나 많은 자원이 필요한가?”를 나타낼 수 있다. 시간과 공간은 반비례적인 경향이 있으나 일반적으로는 시간 복잡도 위주로 알고리즘 효율성을 판단한다.
공간 복잡도(Space Complexity)
공간복잡도란 알고리즘이 수행되는데 필요한 메모리 공간의 양을 말한다.
총 공간=고정 공간 요구+ 가변 공간 요구로 나타낼 수 있다.
->고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.
->가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간을 말한다.
시간 복잡도
시간 복잡도는 이름과 달리 코드의 실제 실행 시간을 계산 할 수 있는것이 아닌, 자료의 크기 n이 증가할 때 수행되는 연산의 개수(연산을 수행하는데 고정된 시간이 걸린다고 가정)를 대략적으로 나타내며 주로 BIG-O(Big O notation)표기법을 사용한다(그 외에도 Ω(Omega), Θ(Theta) 표기법도 존재함).
아래는 입력 자료의 크기 n에 대하여 O(n)의 시간 복잡도에 관한 표이다.
보시다시피 시간복잡도가 복잡한 알고리즘은 n이 커짐이 따라 수행시간이 급격하게 길어지게 된다.
