[Algorithm] 알고리즘이란?

수학 혹은 컴퓨터 과학(Computer Science)에서 

"알고리즘"이란 어떠한 문제를 풀기 위한 "유한한 갯수의 일련의 시퀀스"이다.

 

이때, 알고리즘은 컴퓨터 프로그램으로 대부분 구현되나, 전기 회로 혹은 기계 등등 다른 수단으로도 구현될 수 있다. 

 

특성 

앞서 알고리즘을 "유한한 갯수의 일련의 시퀀스"라고 정의했지만, 여기서 몇가지 조건이 더 붙는다. 

• 입력 : 잘 정의된 입력들을 받아들일 수 있어야 한다.
• 출력 : 정확성을 추론할 수 있는 출력이 있어야 한다.
• 명확성 : 각 단계는 명확하게 정의되어야 한다. 각 단계에서 수행할 작업을 정확하게 지정할 수 있어야 한다. 
• 유한성 : 유한한 수의 명령어의 시퀀스가 수행되면 반드시 종료되어야 한다.
• 유효성 : 모든 명령어는 실행 가능해야 한다.

 

알고리즘 평가 

"유한한 갯수의 시퀀스"가 몇달 혹은 몇년이 걸린다면 "효율적"으로 문제를 풀었다고 할 수 없다. 즉, 알고리즘은 효율성을 고려할 필요가 있으며, 이를 "복잡도"를 통해 평가할 수 있다. 

 

"복잡도"는 시간과 공간을 얼마나 소모하는지를 중점으로 보는데, 이를 각각 시간 복잡도, 공간 복잡도라 부른다. 

 

시간 복잡도 

시간 복잡도는 "알고리즘의 소요시간을 측정"하는데 사용된다. 

 

만약 다음과 같은 알고리즘 있다고 가정해보자. 

int func(int arr[], int n) {
	int cnt = 0;
	
	for(int i = 0; i < n; i++) {
		if(arr[i] % 5 == 0) cnt ++;
	}
	
	return cnt;
}

해당 알고리즘의 시간을 측정하기에는 너무나 많은 변수가 있다.

컴퓨터마다 하드웨어 혹은 OS차이로 인한 실행시간의 차이가 있을 수가 있으며,

같은 컴퓨터라고 할지라도 매 순간 상태가 다르기 때문에, 같은 실행시간을 보장할 수 없다. 

 

따라서, "시간 복잡도"는 문제를 해결하는데 걸리는 시간을 입력에 대한 연산횟수를 통해 나타낸다.

위의 명령어를 본다면, 시간 복잡도는 다음과 같다.

int cnt = 0; // 지역 변수 초기화: 1

우선, cnt 변수의 값을 0으로 선언하고 값을 넣는 과정에서 1번의 연산이 소요된다. 

 

다음으로 for문은 수행하기 전에 i 변수를 초기화하는 연산을 1회 진행한다. 

// i 초기화 연산: 1
for(int i = 0; i < n; i++) {
	// 매 iteration 시작 전 i < n 확인: 1
	
	// arr[i]가 5의 배수인지 비교: 2
	// cnt 증감 연산: 1
	if(arr[i] % 5 == 0) cnt ++;
	// 한번의 iteration이 끝난 후 i 증가: 1
}

이후, for문은 총 n번 반복하게 되는데, 다음과 같은 연산들을 반복한다. 

• 매 iteration 시작 전 i < n 을 만족하는 지 확인하는 연산 1회
• arr[i]를 5로 나누는 연산 1회 
• arr[i]를 5로 나누는 결과를 0과 비교하는 연산 1회
• arr[i]가 5의 배수라면 cnt를 증가시키는 연산 1회
• 매 iteration 완료 후, i++ 하는 연산 1회 

즉, 매 iteration마다 5회의 연산이 진행되며, iteration은 n번 반복하기 때문에 5n + 1번의 연산이 수행된다. 

return cnt;

마지막으로 return 문제에서 1회 연산이 수행된다. 

위의 연산은 n개의 입력에 대해 총 5n + 3번의 연산이 수행된다.

 

공간 복잡도

공간 복잡도는 "알고리즘이 사용하는 메모리 양을 측정"하는데 사용된다.

 

다음과 같은 문자열을 예시로 살펴보자. 

var str = "12345"

8bit의 ASCII를 사용하는 언어에서는 해당 문자열을 널문자를 포함해 6byte로 특정할 수 있지만, 

Swift와 같이 Unicode를 사용하는 언어에서는 UTF8이냐 UTF16이냐 등등 하나의 문자의 길이가 가변적이다. 

 

즉, 언어마다 OS마다 변수하나를 저장하는데 사용하는 메모리양이 다를 수 있다. 

따라서, 시간복잡도와 마찬가지로 "입력에 비례한 메모리 양"을 측정한다.

 

대다수의 경우 시간복잡도와 공간복잡도가 반비례한다. 

과거와 달리, 현재 메모리값이 상당히 저렴하기 때문에 시간복잡도를 많은 경우에 우선적으로 고려한다.

 

점근 표기법

앞서 살펴본 시간복잡도와 공간복잡도는 "입력에 비레하여 측정"한다.

하지만, 모든 알고리즘마다 매번 이렇게 입력에 비례한 메모리양 혹은 연산횟수를 직접 세기에는 쉽지않다.

따라서, 이러한 시간복잡도와 공간복잡도를 표현할때는 점근 표기법을 사용한다. 

 

"점근 표기법"은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법이다.

정확히는 입력 n에 대해서 n을 무한대로 보냈을 때, 수렴하게 되는 새로운 함수로 표기하는 방법이다. 

 

앞선 예시에서 5n + 3은 n을 무한대로 보내게 되면 n에 수렴하게 된다.

즉, 쉽게 말해 가장 영항력 있는 항으로 표기하는 방법이다.

 

이러한 점근 표기법에는 여러가지가 있지만, 알고리즘에서는 크게 3가지를 사용한다. 

• 빅-오 표기법: 점근적 상한
• 빅-오메가 표기법: 점근적 하한
• 빅-세타 표기법: 점근적 평균

 

빅-오(Big-O) 표기법

"빅-오 표기법"은 점근적 상한에 대한 정의이며, 수학적인 정의는 다음과 같다. 

$n_0 \leq n$인 모든 자연수 $n$에 대하여, $f(n) \leq c \cdot g(n)$를 만족하는 양의 상수 $c$와 $n_0$가 존재하면, $f(n) = O(g(n))$ 이다.

 

예시를 통해 살펴보자. $f(n) = 2n^4 + 3n^3 + n + 1$ 라고 가정해보자.

이때, $g(n) = n^4$이라면, $c \geq 3$일때, 기울기가 더 가파르기 때문에, 위의 조건을 만족하는 자연수 $n_0$은 존재한다. 

따라서, $O(n^4)$으로 표기할 수 있다. 

당연하게도 $O(n^5)$, $O(n^6)$, $O(2^n)$ 등등 가능하지만, 점근적 상한을 너무 높게 잡아버리게 되면 알고리즘의 성능을 파악하기 힘들기 때문에 가능한 가장 작은 점근적 상한을 잡는것이 좋다.

 

더욱 쉽게 말해, 적어도 해당 복잡도 안에 든다는 것을 의미한다.

 

빅-오메가(Big-$\Omega$)표기법 

"빅-오메가 표기법"은 점근적 하한에 대한 정의이며, 수학적인 정의는 다음과 같다. 

$n_0 \leq n$인 모든 자연수 $n$에 대하여, $f(n) \geq c \cdot g(n)$를 만족하는 양의 상수 $c$와 $n_0$가 존재하면, $f(n) = \Omega(g(n))$ 이다.

앞선 예시의 $f(n) = 2n^4 + 3n^3 + n + 1$를 다시 한번 살펴보자.

여기서, $g(n) = n^4$이라면, $c \leq 2$일때, 위의 조건을 만족하는 자연수 $n_0$는 존재한다. 

따라서, $\Omega(n^4)$으로 표기할 수 있다. 

마찬가지로 $\Omega(n^3)$, $\Omega(n)$, $\Omega(1)$ 등등 가능하지만, 점근적 하한을 너무 낮게 잡으면 성능을 파악하기 어려워진다. 

 

쉽게 말해, 적어도 해당 복잡도보다는 크다는 것을 의미한다.

 

빅-세타(Big-$\Theta$)표기법

"빅-세타 표기법"은 점근적 평균에 대한 정의이며, 수학적인 정의는 다음과 같다.

$n_0 \leq n$인 모든 자연수 $n$에 대하여, $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$를 만족하는 양의 상수 $c_1$, $c_2$와 $n_0$가 존재하면, $f(n) = \Theta(g(n))$ 이다.

마찬가지로 $f(n) = 2n^4 + 3n^3 + n + 1$를 예시로 들어보자. 

여기서, $g(n) = n^4$이라면, $c_1 \leq 2$이고, $c_2 \geq 3$일때, 위의 조건을 만족하는 자연수 $n_0$는 존재한다.

따라서, $\Theta(n^4)$으로 표기할 수 있다.

 

평균적으로 해당 복잡도 안에 든다는 것을 의미한다.

 

빅-오, 빅-오메가, 빅-세타는 최악, 최선, 평균을 의미하지 않는다.  

수많은 곳에서 빅-오는 최악의 경우, 빅-오메가는 최선의 경우, 빅-세타는 평균의 경우라고 정의하는 경우가 많다.

하지만, 이러한 해석은 틀린 해석이다. 

 

다음과 같은 코드를 살펴보자.

func index(of target: Int, in array: [Int]) -> Int {
	for idx in (0..<array.count) {
		if arr[idx] == target { return idx }
	}
	
	return -1
}

앞서, 점근적 상한인 빅-오는 "적어도 이 복잡도 안에 든다는 것"을 의미한다고 했지만, 이때의 상한은 최악의 경우를 의미하지 않는다.

만약 target이 1번째 인덱스에 존재하는 경우, 해당 함수는 1번만에 for문이 진행될것이다. 

하지만, 최악의 경우 맨끝 인덱스에 존재하는 경우, array의 원소 갯수 만큼 for문을 돌게 될것이다.

 

시간복잡도를 예시살펴보자면, 다음과 같이 최선, 최악의 경우 각기 다른 시간복잡도를 가지게 될 것이다.

즉, 복잡도를 논하기 위해서는 최선, 최악, 평균에 대한 시나리오부터 고려해야 한다. 

 

빅-오 표기법은 "최선, 최악 혹은 평균의 경우 적어도 이 복잡도 안에 든다는 것"을 의미한다.

따라서, 위의 알고리즘은 최선의 경우 $O(1)$이고, 최악, 평균은 $O(n)$에 동작한다고 말할 수 있다.

다른 점근 표기법도 마찬가지로 이런 입력에 대한 시나리오부터 고려하는 것이 맞다. 

 

대표적인 예시로 퀵소트 알고리즘의 경우, 최선, 평균의 경우 $O(n logn)$이며, 최악의 경우 $O(n^2)$으로 동작한다. 

즉, 최선과 평균적인 입력에 대하여 적어도 $n logn$안에 동작하며, 최악의 경우에는 적어도 $n^2$안에 든다는 의미이지,

이를 $\Omega(n logn)$, $\Theta(n logn)$, $O(n^2)$으로 표기하지는 않는 이유이다.

 

 

Reference

위키백과

• Algorithm
• Time Complexity
• Space Complexity