Algorithm Analysis - Correctness, Complexity, Optimality

컴퓨터 알고리즘이란 문제를 해결하기 위해 정의한 Instruction Sequence를 말한다.

알고리즘을 작성했다면 알고리즘이 문제의 요구조건을 만족하는지(Correctness),
얼마나 많은 연산이 필요한지(Complexity), 문제의 복잡도와 얼마나 가까운지(Optimality) 분석해야 한다.

그럼 이제 알고리즘을 세워보고 어떻게 분석하는지 알아보자.

 

Algorithm

n개의 entry를 갖는 non-ordered array E에서 index 값이 K인 entry를 찾는 문제를 해결해보자.

int seqSearch(int* E, int n, int K) {
	int ans, index;
	ans = -1;
	for (index = 0; index < n; i++) {
		if (K == E[index]) {
			ans = index;
			break;
		}
	}
	return ans;
}

알고리즘은 단순하게 K 값과 일치하는 entry가 나올 때까지 모든 entry를 탐색하도록 작성하였다.

 

Analysis - Correctness

먼저 구현한 알고리즘, instruction sequence가 문제를 올바르게 해결하는지 확인해야 한다.

이를 증명하기 위해선 문제에서 주어진 preconditions(inputs)를 만족하는지 확인하고,

올바르게 postconditions(outputs)를 만족하도록 변환하는지 확인하면 된다.

 

예시 문제에서는 unordered array E(input)와 찾으려는 key 값 K가 주어졌을 때,

key 값이 K와 일치하는 entry의 index(output)를 올바르게 반환하는지 확인하면 된다.

 

Analysis - Complexity

다음으로 구현한 알고리즘의 작업량(complexity)을 계산함으로써 알고리즘이 얼마나 효율적인지 측정해야 한다.

작업량이 많아질수록(complexity가 증가할수록) 수행 시간이 길어지므로 효율이 낮아진다고 할 수 있다.

 

complexity는 컴퓨터의 성능이나 프로그래밍 언어 등과는 독립적이며 일반적으로 input data의 크기에 비례한다.

또한 상황에 따라 input data의 조건이 complexity에 영향을 줄 수 있다.

Complexity 계산

complexity를 계산하기 위해서는 먼저 1) 주어진 문제의 basic operation을 파악해야 한다.

알고리즘을 수행하는데 필요한 basic operation의 갯수를 통해 complexity를 추정할 수 있다.

 

다음으로, 2-1) 최악의 경우(worst-case)나 2-2) 평균적인 경우(average-case)의 작업량을 계산한다.

 

input size가 n일 때, 알고리즘의 worst-case complexity W(n)과 average-case complexity A(n)은 위와 같이 계산한다.

D는 input element의 집합, I는 element, t(I)는 basic operation의 수, Pr(I)는 input I가 발생할 확률이다.

 

즉, worst-case complexity는 임의의 input element I에 대해 알고리즘을 수행하는데 필요한 basic operation의 수 중 최댓값을 의미하며, average-case complexity는 (임의의 input element I가 나타날 확률 × I에 대해 알고리즘을 수행하는데 필요한 basic operation의 수)의 총합을 의미한다.

 

Example

이제, 위에서 작성한 알고리즘을 예로 살펴보자.

 

1) 먼저, key 값을 비교하는 연산이 가장 많이 사용되므로 비교 연산을 basic operation으로 설정하자.

 

2-1) worst-case는 array 안에 key 값이 K인 element가 존재하지 않는 경우이며, input array의 모든 element와 비교 연산을 수행해야 하므로 n번의 basic operation이 필요하다.

 

2-2) average-case는 array 안에 key 값이 K인 element가 존재하는 경우와 존재하지 않는 경우를 나누어 계산해야 한다.

 

이를 앞서 말한 식과 같이 표현하면 위와 같다.

먼저, 두 가지 경우 각각의 average-case complexity를 구해보자.

 

 

① array 안에 존재하는 key 값이 주어지는 경우의 수는 n이고, 각각의 평균 작업량은 다음과 같이 구할 수 있다.

n개의 element 중 임의의 index i인 element 하나를 고를 확률은 1/n이고, 이 element를 찾기 위해 필요한 작업량은 해당 element보다 index가 작은 element들과 자신의 key값까지 비교해야 하므로 i+1번의 비교 연산이 필요하다.

 

따라서 index 0부터 n-1, 총 n개의 경우에 대한 평균 작업량은 (n+1)/2이다.

 

 

② 다음으로 존재하지 않는 key 값이 주어지는 경우의 수는 1이고, 작업량은 모든 element와 비교해봐야 하므로 n번의 비교 연산이 필요하다. 따라서 이 경우 평균 작업량은 1×n = n이다.

 

 

마지막으로 존재하는 key 값이 주어질 확률이 q라고 하면, 존재하지 않는 key 값이 주어질 확률은 1-q이므로 전체 경우의 average-case complexity는 다음과 같다.

 

 

Classifying Functions (Asymptotic Notation)

복잡도를 표현할 때는 일반적으로 점근적 형태의 함수 집합으로 표현한다. (점근 표기법)

점근적 형태로 표현하는 이유는 constant factor는 수행시간에 큰 영향을 주지 않기 때문이다.

 

함수의 집합은 아래와 같은 형태로 나누어 표현한다.

 

g보다 점근적 증가율이 같거나 빠른 함수의 집합 Ω(g) - Big Omega
g와 점근적 증가율이 같은 함수들의 집합 θ(g) - Big Theta

g보다 점근적 증가율이 같거나 느린 함수의 집합 O(g) - Big Oh

 

예를 들어 생각해보자.

 

앞서 말했듯 순차 탐색의 worst-case complexity는 input size n에 비례한다. (증가율이 n)

하지만 찾는 key 값을 가진 entry가 맨 앞에 있을 경우에는 1번의 연산만 필요하다. (증가율이 0)

따라서 문제의 복잡도는 n보다 같거나 느린 증가율을 갖는다고 할 수 있으므로 O(n)으로 표현할 수 있다.

 

이처럼 일반적으로 문제나 알고리즘의 complexity를 얘기할 때는 worst-case complexity를 이야기하기 때문에,

worst-case complexity가 n일 경우 '이 문제(알고리즘)의 complexity는 O(n)이다' 라고 주로 표현한다.

 

Analysis - Optimality

알고리즘의 복잡도를 구했다면 문제의 복잡도와 비교하여 얼마나 효율적인지 분석해야 한다.

구현한 알고리즘의 worst-case complexity가 문제의 complexity에 가까울수록 효율적이라고 볼 수 있다.

complexity가 같다면 구현한 알고리즘이 optimal 하다고 할 수 있고, 같지 않다면 더 좋은 알고리즘이 있을 수 있다.

 

앞서 해결한 문제와 알고리즘의 시간복잡도를 예로 비교해보자.

순차 탐색 문제의 경우 최악의 경우 모든 entry를 살펴봐야 하므로 worst-case complexity는 n이다.

작성한 알고리즘의 worst-case complexity는 앞서 구했다시피 n이므로 문제의 복잡도와 같다.

따라서 구현한 알고리즘은 optimal 하다고 할 수 있다.