알고리즘 성능 분석

알고리즘 성능 분석 (Performance Evaluation of Algorithm)

---

알고리즘은 문제 해결을 하기 위한 레시피와 같다. 그러나 레시피는 세상에 하나만 존재하지는 않는다. 음식을 만들 때 각자의 방식이 있듯이 하나의 문제에 대한 알고리즘도 다양하게 나올 수 있다. 우리가 1부터 100을 더할 때 정말로 1부터 100을 다 더할 수 있지만 공식을 통해 빠르게 풀어낼 수도 있다. 다양한 알고리즘들 중에 문제를 비효율적으로 해결하는 알고리즘을 가지고 문제를 해결하고 싶은 사람은 없을  것이다. 그렇기에 어떤 기준을 가지고 알고리즘을 평가하게 되는데 그 기준이 공간 복잡도(space complexity)와 시간 복잡도(time complexity)이다.

 

 공간 복잡도(Space Complexity)란 알고리즘이 실행되는 동안 사용되는 최대 메모리 사용량을 말한다. 1~100의 합을 구하는 프로그램을 만들 때 정수 배열 100개를 선언하고 합을 sum이라는 정수 변수에 저장한다면 101 * 4byte의 공간을 차지하게 된다. 하지만 n(n + 1)/2를 이용하면 4byte만 사용하면 된다. 초기 컴퓨터의 경우, 메모리 값이 비싸기 때문에 공간 복잡도가 알고리즘을 평가하는 중요한 요소중에 하나였지만 최근에는 메모리 가격이 저렴해지면서 시간 단축을 위해 공간 복잡도를 포기하는 경우가 많아졌다.

 

 시간 복잡도(Time Complexity)란 프로그램화된 알고리즘의 실행 시간을 말한다. 여기서 시간은 실제 지나간 시간을 의미하는 것이 아니라 실행문의 수를 말한다. 프로그램이 동작하는 시간은 컴퓨터, 사용 언어, 사용 컴파일러등 종속적인 요인이 많아 정확한 시간을 측정하기 힘들다. 그래서 학자들은 한 개의 실행문을 1로 두고 프로그램이 데이터를 처리하는 동안 몇 개의 실행문을 실행하는가를 통해 측정을 하게 된다. 실행문이란 1개의 명령문을 의미한다.

 

void searchNumber(int max, int n, int numArray[]){
for(i = 1; i <= max; i++)
    if(i == numArray[i])
    	return i
}

 

 

 알고리즘을 분석할 때는 최악의 경우 분석(worst-case analysis), 평균의 경우 분석(everage-case analysis), 최선의 경우 분석(best-case analysis) 3가지로 나눌 수 있다. 그러면 알고리즘을 어떻게 평가하는지 알아보자. 위 알고리즘은 1~max까지 정수 배열에서 n을 찾는 알고리즘이다. 최악의 경우는 for문 전체를 도는 것이기 때문에 시간 복잡도는 max이다. 최선의 경우는 for문을 1번만 도는 것이기 때문에 시간 복잡도는 1이다. 평균적인 경우는 for문을 1번 도는 경우, 2번 도는 경우 ... max번 도는 경우를 모두 합하여 평균을 내는 것이기 때문에 시간 복잡도는 (max + 1) / 2가 된다. 

 

 

점근적 표기법 (Asymptotic Notation)

---

앞서 알고리즘을 설명하는 방법으로 최악, 평균, 최선의 경우를 소개하였다. 하지만 앞선 방법처럼 실행문의 수를 모두 계산하여 표기하는 방법은 효율적이지 않을 뿐더러 대부분의 알고리즘이 복잡한 형태를 이루기 때문에 그 수를 정확하게 표기할 수 없다. 그렇기 때문에 알고리즘을 표기할 때는 비교적 간단한 함수 형태로 만들어 이를 통해 알고리즘을 비교하게 된다. 이때 간단한 함수 형태로 표기하는 방법을 점근적 표기법이라고 한다. 점근적 표기법에는 Big-O, little-o, Big-Ω, little-ω, Big-Θ 5가지가 있다. 

 

 

Big-O 표기법 (Big-O notation)

Big-O 표기법은 알고리즘의 점근적 상한을 나타내는 표기법이다. 즉, 알고리즘이 가장 최악의 상황일 때 Big-O와 같은 증가 형태를 지닌다는 의미이다. 수학적인 정의는 다음과 같다.

정의
n ≥ n₀인 모든 n에 대해 f(n)  ≤   c · g(n)를 만족하는 양의 상수 c와 n₀가 존재하면 f(n) = O(g(n))이다.

Big-O표기법은 알고리즘을 나타낼 때 가장 많이 쓰이는 표기법으로 다음 포스팅에서 더 자세하게 다루겠다.

 

 

Little-o 표기법 (Little-o notation)

little-o 표기법은 Big-O표기법보다 더 넓은 범위의 상한 표기법이다. 즉, 어떠한 상황에도 알고리즘은 little-o를 넘어가지 않는다는 의미이다. 수학적 정의는 다음과 같다.

정의
n ≥ n₀인 모든 n에 대해  f(n) < c · g(n)를 만족하는 양의 상수 n₀가 모든 양의 상수 c에 대해 존재한다면 f(n) = o(g(n))이다.

little-o 표기법은 최악의 경우에도 알고리즘의 성능이 표기 성능보다 더 좋으니까 좋은 표기법이 아니냐는 질문이 생길 수 있다. 그렇다면 정의를 잘 살펴보아야 한다. f(n) = 2n + 3이라고 주어졌을 때 f(n)을 little-o로 표기하기 위해서는 g(n)이 모든 양의 상수 c에 대해 위 정의를 만족해야 하므로 g(n) = n^2으로 표현할 수 있다. 따라서 f(n) = o(n^2)으로 표현할 수 있다. f(n)의 증가량과 g(n)의 증가량은 상당히 많은 차이가 난다. 그러므로 little-o표기법은 본래 성능에서 어떤 범위로 잡느냐에 따라 실제 성능과 차이가 많이 나기 때문에 Big-O보다는 상대적으로 자주 쓰이진 않는다.

 

 

Big-Ω 표기법 (Big-Ω notation)

Big-Ω 표기법은 점근적 하한을 나타내는 표기법이다. 즉, 알고리즘이 가장 빠를 때를 표기한 것이다. 수학적 정의는 다음과 같다.

정의
n ≥ n₀인 모든 n에 대해 f(n) ≥ c · g(n)를 만족하는 양의 상수 c와 n₀가 존재하면 f(n) = Ω(g(n))이다.

f(n) = 2n + 3이라고 주어진다면 위 정의를 만족하는 g(n)은 g(n) = n이 될 것이다. 따라서 f(n) = Ω(n)으로 표현할 수 있다. 알고리즘이 항상 최선의 경우에서만 작동하지 않기 때문에 최악의 경우 얼마나 시간이 걸릴지 예상할 수 없어 Big-Ω 표기법은 거의 사용되지 않는다.

 

 

Little-ω 표기법 (Little-ω notation)

little-ω 표기법은 Big-Ω 표기법보다 더 넓은 범위의 하한 표기법이다. 즉, 아무리 빨라도 little-ω보다는 느리다는 것이다.

수학적 정의는 다음과 같다.

정의
n ≥ n₀인 모든 n에 대해  f(n) > c · g(n)를 만족하는 양의 상수 n₀가 모든 양의 상수 c에 대해 존재한다면 f(n) = o(g(n))이다.

little-ω로 f(n) = 2n + 3을 표기하면 위 정의를 만족하는 g(n) = 1이므로 f(n) = ω(1)로 표현할 수 있다.  little-ω 표기법도 우리가 원하는 정보를 주지는 못할 것이다. 우리는 아무리 느려도 어느 정도의 성능 보장을 원한다. 아무리 빨라도 일정 수치보다는 느리다는 정보는 우리가 알고리즘을 판단함에 있어서 유용한 정보가 되지는 못한다.

 

 

Big-Θ 표기법 (Big-Θ notation)

Big-Θ 표기법은 점근적 평균을 나타내는 표기법이다. 즉, 이 알고리즘은 평균적으로 이정도의 속도를 낸다는 것을 표기하는 것이다. 수학적 정의는 다음과 같다.

정의
n ≥ n₀인 모든 n에 대해 c · g(n) ≤ f(n) ≤ d · g(n)를 만족하는 양의 상수 c, d와 n₀가 존재하면 f(n) = Θ(g(n))이다.

f(n) = 2n + 3을 Big-Θ로 표기하게 되면 f(n) = O(n)이다. 앞서 f(n) = Ω(n)으로 표기할 수 있음을 알았다. 그러면 Big-Θ 표기법의 정의에 따라 부등식의 왼쪽은 Ω(n)과 같고 부등식의 오른쪽은 O(n)와 같다. 그러므로 f(n) = Θ(n)으로 표기할 수 있다.