AL02 - 알고리즘의 성능 분석

성능 분석이란?                              

  어떠한 문제를 해결할 방법은 많지만 문제를 해결하는데 너무 오랜 시간이 걸려서는안된다.

따라서 우리는 문제를 가장 효율적이고 빠르게 해결할 수 있는 방법을 찾아야 하는데 이 과정에서 여러 

알고리즘의 성능을 분석하고 비교하게 된다.

  그렇다면 알고리즘의 성능은 어떻게 분석할까?

알고리즘의 성능을 분석하는 판단 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있다.

• 정확성 :  올바른 자료가 입력되었을때 유한한 시간 내에 올바른 결과를 도출하는가?

• 명확성 : 알고리즘이 이해하기 쉽고 명확하게 작성되었는가?(명확한 알고리즘은 이해와 변경이 쉽다.)

• 수행량 : 알고리즘의 주요 연산이 얼마나 반복되는가?

• 메모리 사용량 : 알고리즘이 문제를 해결하기 위해 얼마나 많은 메모리 공간을 필요로 하는가?

• 최적성 : 알고리즘이 문제 해결의 조건에 최적으로 부합하는가?(종합적 판단 요구)

  이러한 기준들을 토대로 알고리즘을 분석하는 방법에는 크게 두가지가 있다.

 1. 공간 복잡도(Space Complexity)

  공간 복잡도(Space Complexity)는 알고리즘을 프로그램으로 실행하여 완료하는데 필요한 총 저장공간(메모리의 

사용량)을 의미한다. 공간 복잡도는 필요한 고정공간과 가변공간을 합하여 구한다. 

  고정공간은 프로그램의 크기나 입출력 횟수와 관련없이 고정으로 필요한 저장 공간으로 프로그램 저장공간과 

변수 및 상수를 저장하는 공간이다. 

가변공간은 실행 과정에서 사용하는 자료와 변수를 저장하는 공간과 함수를 실행하는 데 관련 있는 정보를 저장하는 공간이다.

  만약 어떠한 프로그램을 실행하는데 n개의 데이터를 저장하는 배열을 사용한다면 이 프로그램의 공간복잡도는

가변 공간인 배열의 크기 n과 고정공간의 크기를 더해 구한다.

 2. 시간 복잡도(Time Complexity)

  시간 복잡도(Time Complexity)는  알고리즘을 프로그램으로 실행하여 완료하는데 까지 소요되는 시간이다. 시간 복잡도는 프로그램의 컴파일 시간과 실행시간을 더해 구한다.

  컴파일 시간은 프로그램의 특성과 큰 관련이 없으므로 고정된 같은 시간으로 가정한다. 일단 컴파일이 되면 

프로그램을 수정하지 않는 한 추가로 컴파일 작업을 하지 않으므로 시간 복잡도에서는 컴파일 시간을 의미있는 

시간으로 간주하지 않는다. 

  실행 시간은 같은 프로그램이더라도 실행되는 컴퓨터의 성능에 따라 달라질 수 있기 때문에 실제 실행시간을 

측정하는 것이 아니라 명령문의 실행 빈도수를 계산하여 추정한다.

  시간 복잡도에서는 정확한 실행 시간이 아닌 명령문의 실행 빈도수를 계산한다.

명령문의 예로는 지정문, 조건문, 반복문, return문, 제어문 등 컴퓨터 프로그램에서 사용되는 다양한 명령이 있다.

이중 지정문, 조건문, return문 등은 실행 하는데  걸리는 시간이 미미하기 때문에 하나의 단위시간으로 계산한다.  

자료(Data)의 양이 늘어나면 반복문의 실행 빈도수 또한 증가하기 때문에 보통은 자료의 양 n에 대한 반복문의

반복 횟수를 실행 시간으로 계산한다.

  예를 들어 다음의 코드는 크기가 n인 배열arr의 거품 정렬(Bubble Sorting) 함수이다. 

    
bubbleSort(int *arr, int n)
{
	int i = 0, j = 0;
	int temp;

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n-1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

위 코드의 경우 변수 i가 0 ~ n-1 까지 n번 반복되고, 변수 j가 0 ~ n-2까지 n-1번 반복 된다.

반복문 이외의 조건문이나 실행문의 경우 단위시간인 1 로 계산하기 때문에 위 함수의 총 실행시간은

n * (n-1) + 6 = n ^ 2 - n + 6이 된다.

 배열의 크기인 n이 작을 땐 아주 작은 시간이 소모 되지만 n이 커짐에 따라 실행시간은 기하급수적으로 늘어난다.

알고리즘 성능 분석 표기법        

   알고리즘 성능을 비교하기 위해 메모리 사용공간을 비교한 공간 복잡도(Space Complexity)와 시간 복잡도(Time Complexity)를 구하는데, 일반적으로 알고리즘의 주요 성능차이는 실행 시간 차이에서 발생한다. 

따라서 알고리즘을 비교하기 위한 성능 분석 표기는 시간 복잡도(Time Complexity)의 표기를 의미한다.

  

  시간 복잡도(Time Complexity)는 실행 시간에서 입력크기 n에 대한 실행 시간의 증가율만 분석하는 점근적 분석(Asymptotic Analysis)이므로, 실행 시간의 상수항과 계수는 무시하고 n의 증가에 따라 증가율이 가장 

큰 하나의 항에 대해 차수 표기법(Order Notation)으로 시간 복잡도를 표기한다.

이러한 방식의 시간 복잡도 표기법에는 다음의 세가지 방법이 있다.

1. 빅-오 표기법(Big-Oh Notaton)

  

  빅-오 표기법(Big-Oh Notation)은 O(f(n))과 같이 표기하며, "Big-Oh of f(n)"으로 읽는다.

만약 실행시간이 n ^ 2이라면 O(n ^ 2)로 표기하고 "Big-Oh of n ^ 2"으로 읽는다.

빅-오 표기법의 수학적 정의는 다음과 같다.

  수학적 정의에서 알 수 있듯이 빅-오 표기법은 함수의 상한을 나타내기 위한 표기법이다.

즉, 최악의 경우에도 g(n)의 시간 안에는 알고리즘이완료된다는 것을 보장한다.

  

  어떠한 프로그램을 빅-오 표기법으로 나타내는 방법은 실행 시간을 구하고 그 실행시간에서 가장 큰 영향을 주는 즉, 가장 차수가 높은 항을 선택하여 계수는 생략하고 O의 괄호 안에 표기한다.

위 거품 정렬 함수의 경우 실행시간이 n ^ 2 - n +6 이기 때문에 빅-오 표기법으로 나타낼 시 O(n ^ 2)가 된다.

2. 빅-오메가 표기법(Big-Omega Notaton)

  빅-오메가 표기법(Big-Omega Notation)은 Ω(f(n))과 같이 표기하며, "Big-Omega of f(n)"으로 읽는다.

만약 실행시간이 n ^ 2이라면 Ω(n ^ 2)로 표기하고 "Big-Omega of n ^ 2"으로 읽는다.

빅-오메가 표기법의 수학적 정의는 다음과 같다.

   빅-오메가 표기법은 빅-오 표기법과 반대로 함수의 하한을 나타내기 위한 표기법이다.

즉, 어떤 프로그램의 시간 복잡도가 Ω(g(n))이라면, 이 프로그램은 적어도 g(n)의 시간을 필요로 한다는 뜻이다.

  어떠한 프로그램을 빅-오메가 표기법으로 나타내는 방법은 실행 시간을 구하고 그 실행시간에서 가장 큰 영향을 주는 즉, 가장 차수가 높은 항을 선택하여 계수는 생략하고 Ω의 괄호 안에 표기한다.

위 거품 정렬 함수의 경우 실행시간이 n ^ 2 - n +6 이기 때문에 빅-오 표기법으로 나타낼 시 Ω(n ^ 2)가 된다.

3. 빅-세타 표기법(Big-Theta Notaton)

  빅-세타 표기법(Big-Theta Notation)은 θ(f(n))과 같이 표기하며, "Big-Theta of f(n)"으로 읽는다.

만약 실행시간이 n ^ 2이라면 θ(n ^ 2)로 표기하고 "Big-Theta of n ^ 2"으로 읽는다.

빅-세타 표기법의 수학적 정의는 다음과 같다.

   빅-세타 표기법은 함수의 상한과 하한이 정확히 같은 차수를 나타내기 위한 표기법이다.

즉,  f(n) =   θ(g(n))이라면,  f(n) = Ω(n)이면서 f(n) = O(n)이어야 한다.

  어떠한 프로그램을 빅-세타 표기법으로 나타내는 방법은 실행 시간을 구하고 그 실행시간에서 가장 큰 영향을 주는 즉, 가장 차수가 높은 항을 선택하여 계수는 생략하고 θ의 괄호 안에 표기한다.

위 거품 정렬 함수의 경우 실행시간이 n ^ 2 - n +6 이기 때문에 빅-오 표기법으로 나타낼 시 θ(n ^ 2)가 된다.

  시간 복잡도를 정확하게 계산할 수 있다면 빅-세타 표기법을 사용하면 된다.

하지만 시간 복잡도를 정확하게 계산하기 어렵다면 프로그램의 상한을 구하여 빅-오 표기법을 사용하거나 하한을 구하여 빅-오메가 표기법을 사용한다.

일반적으로는 최악의 상황을 고려한 빅-오 표기법을 사용한다.

  알고리즘의 종류에 따라 1, log n, n, nlogn, n ^2, n ^3, 2 ^n, n! 등의 실행시간을 가진다.

위의 표와 그래프는 데이터의 양 n이 증가함에 따라 각각의 시간복잡도가 얼마나 많은 명령을 수행하는지를 

나타낸 표이다.

데이터의 수가 적을 땐 알고리즘간의 수행시간 차가 크지 않지만 데이터가 늘어남에 따라 알고리즘의 수행 시간은 기하급수적으로 늘어남을 알 수 있다.