[2] 알고리즘의 복잡도

책에서는 알고리즘이 얼마나 효율적인가를 시간계산량과 영역계산량이라고 소개했는데 사실 이보다는 시간복잡도, 공간복잡도가 더 익숙하다.

 

따라서, 이 용어로 설명을 하자면

시간복잡도는 알고리즘을 실행시 소요되는 시간을 말한다.(여기서 말하는 시간은 실제 경과된 시간이 아니 처리해야 할 일의 양을 의미)

 

프로그램을 실행시켜 종료까지의 시간을 구할 수도 있지만, 아래와 같은 문제가 있다.

1. 실행하는 컴퓨터의 성능차이

2. 주변기기와 데이터의 입출력에 걸리는 시간

 

컴퓨터마다 위 조건들이 다르기 때문에 처리속도만 가지고는 객관적으로 측정을 하기가 어렵다.

따라서 연산, 조건비교, 변수대입 등과 같은 처리들을 하나의 단위로 삼아서 실행횟수를 측정하여 알고리즘의 효율성을 따진다.

 

공간복잡도는 알고리즘 실행시 사용되는 메모리 영역의 크기를 뜻한다.

 

일반적으로는 계산량이 문제가 될 경우 시간복잡도로 평가한다.

 

같은 계산이라도 1부터 N까지 더하는 연산은 N의 수에 따라 양이 많아지게 되므로 N번의 연산을 해야하고 N(N+1)/2 는 항상 고정된 수의 연산만해서 같은 값을 얻을 수 있다.

이런 결과들을 알고리즘에서는 보통 빅오(big-O)표기법으로 나타내는데 n개의 데이터의 계산량이 n에 비례하면 O(n)이라고 나타내고, n의 값에 관계없이 계산하면 O(1)이라고 한다.

 

만약 이진탐색처럼 N개의 범위에서 1번 검색할 때 마다 절반씩 범위가 좁혀지는 경우 범위가 1이 될 때까지 k번 연산을 진행하면, N*(1/2)^k = 1이고, N = 2^k 이므로

k = log2N

따라서 연산량은 O(log2N)이 된다.

 

계산량의 대소관계는 아래와 같다.

O(1) < O(log2n) < O(n) < O(n*log2n) < O(n^2) < O(2^n)

 

이처럼 시간복잡도, 공간복잡도 같은 객관적인 수치로 알고리즘의 연산량이나 사용 메모리 공간등을 나타냄으로써 알고리즘이 얼마나 효율적인지 알 수 있기 때문에 알고리즘마다 얼만큼의 효율을 가지는지 따져보고 알아 두는것도 프로그래밍을 할 때 상당한 도움이 될 것 같다.