알고리즘의 성능 분석 (시간복잡도 계산 방법)

# 어떤 알고리즘이 성능이 좋을까?

알고리즘의 성능을 분석하기 위해서 여러 방법을 쓸 수 있다. 가장 쉬운 방법은 알고리즘의 실제 실행시간을 측정해보는 것이다. 실행시간을 비교하면서, 어떤 알고리즘이 성능이 좋고 빠른지 알 수 있다. 하지만 이 방법에는 크게 두 가지 단점이 있다. 하나는 실제로 알고리즘을 구현해야 한다는 것, 다른 하나는 컴파일러나 실행 기기에 실행시간이 의존한다는 사실이다. 이러한 한계를 극복하기 위하여 복잡도 분석을 사용할 수 있다.

 

# 복잡도 분석

실제로 구현하지 않고, 실행환경에 의존하지 않으면서 알고리즘의 성능을 분석할 수 있는 방법이다. 알고리즘에서 실행되는 산술 동작의 갯수를 세보는 방법이다. 복잡도 분석에는 두 가지 종류가 있는데, 시간 복잡도 분석과 공간 복잡도 분석이다. 시간 복잡도는 실행 시간을 계산한다. 공간 복잡도는 실행에 필요한 메모리 공간을 계산한다. 시간복잡도와 공간복잡도는 항상 그렇지는 않지만, 때때로 반비례 관계이다. 시간복잡도가 높은 알고리즘을 메모리를 더욱 많이 사용해서 시간 복잡도를 낮출 수 있다. 혹은 메모리를 더 적게 사용하고 시간 복잡도를 높일수도 있다. 하지만 알고리즘에서 공간 복잡도를 판단하는 것은 매우 어렵기 때문에, 대부분 시간 복잡도를 주요하게 고려한다. 

 

# 복잡도 분석 예시

 - 알고리즘 실행 시 실행되는 대입, 덧셈, 곱셈, 나눗셈 등의 연산 횟수를 센다. 

* n 은 입력의 갯수이다.

알고리즘 A	알고리즘 B	알고리즘 C
sum ← n*n;	sum ← 0; for i in 1 to n do     sum ← sum + n;	sum ← 0; for i in 1 to n do     for j in 1 to n do         sum ← sum + 1;

알고리즘 A, B, C가 위와 같을 때, 각각의 연산 횟수는 아래와 같다.

 

	알고리즘 A	알고리즘 B	알고리즘 C
대입	1	n + 1	n * n + 1
덧셈		n	n * n
곱셈	1
나눗셈
총합	2	2n + 1	2 n * n + 1

 

n이 증가할 때 연산횟수 그래프는 다음과 같다. n이 커질수록 알고리즘의 실행시간은 크게 차이가 날 것으로 예상된다.

 

# 점근 표기법

n 이 충분히 크면, 가장 높은 차수가 가장 영향력이 있고, 나머지는 상대적으로 무시할만하다. 예를 들어,

T(n) = n^2 + n + 1이고, n이 1000일때, T(n) = 1,001,001 이다. n^2 은 1000000이고, n 은 1000이 된다. n 은 T(n)에서 1% 정도밖에 차지하지 않는다. 따라서, 가장 영향력이 큰 차수만 고려해도 충분하다. 점근 표기법에는 세 가지가 있다.

 

- 빅 오 표기법 (Big O Notation) : 최악의 경우의 성능. 수행 시간의 상한

- 빅 오메가 표기법 (Big Ω Notation) : 최선의 경우의 성능, 수행 시간의 하한

- 빅 세타 표기법 (Big θ Notation) : 상한과 하한을 모두 만족시키는 교집합

 

* 최선의 경우 성능보다는, 최악의 경우 성능(빅오 표기법)에 더 관심이 큼

 

# 빅오표기법 (Big O Notation)

빅오표기법을 수학적으로 정의할 수도 있지만, 가장 단순하게 설명하면 그냥 f(n)의 최고차 항이라고 이야기 할 수 있다.

 

f(n) = 5 일 때, O(1)f(n) = 2n+ 10일때, O(n)f(n) = 2n^2 + n + 1 일 때, O(n^2)f(n) = 5*2^n + 10n^2+100 일 때, O(2^n)

 

몇몇 빅오표기법의 종류를 그래프로 나타내면 다음과 같다.

 

 

알고리즘의 성능 표현

빅오표기법	알고리즘
O(1)	해시테이블
O(log n)	이진 탐색
O(n)	순차 탐색
O(n log n)	병합 정렬, 퀵 정렬
O(n^2)	버블 정렬, 삽입 정렬
O(n^3)	행렬 곱셈