Algorithm Analysis

왜 알고리즘을 분석해야 하는가?

알고리즘 분석을 하는 것은 프로그래머에게 매우 중요한 일이다. 알고리즘을 분석할 줄 알아야, 알고리즘의 성능을 체크한 뒤 향상시킬 수 있고, 어느 알고리즘이 더 좋은 알고리즘인가에 대한 판단을 내릴 수 있기 때문이다. 최근 점점 더 방대한 양의 데이터가 컴퓨터 작업에 이용되면서 효율적인 알고리즘 작성의 중요성은 이전보다도 훨씬 높아졌다. 

---

알고리즘 분석에는 총 3가지 측면이 있다. 

1. 시간 복잡도
2. 공간 복잡도
3. 최적성

---

시간 복잡도

먼저, 시간 복잡도에 대해 이야기해 보고자 한다. 사실 세 개념 중에서도 가장 많이 쓰이고, 그만큼 중요한 것이 바로 이 시간 복잡도이다. 시간 복잡도는 간단히 말해 "선택받은 연산자의 시행 횟수"라고 할 수 있다. 선택받은_ 이라는 단어에서 알 수 있듯, 시간 복잡도는 프로그램이 수행되는 시간을 엄밀하게 재는 것이 아니라, 수행 시간에 가장 큰 영향을 미칠 것으로 예상되는(연산의 총 개수에 비례하는) 연산자를 몇 개 선택한 다음, 해당 연산자가 인풋에 어떻게 비례해서 수행되는지를 계산한다. 시간 복잡도를 분석하는 방법에도 3가지가 있지만, 주로 첫 번째 방법을 가장 많이 사용하게 된다.

시간 복잡도 - 최악의 시간 복잡도 (Worst time complexity)

시간 복잡도를 분석하는 방법 중 가장 많이 쓰이는 분석 방법이다. 이는 같은 크기의 인풋 n 을 받더라도, 입력 상황에 의해 수행해야 하는 연산의 횟수가 달라질 때, 그 중 가장 많은 연산을 사용해야 하는 경우의 연산 횟수를 해당 알고리즘의 시간 복잡도로 보는 방법이다. 예를 들어, 앞서 살펴본 예시 중, linear search 로 원하는 값을 찾던 알고리즘의 시간 복잡도를 생각해 보자. 

1) n개 요소를 가진 배열이 인풋으로 주어졌을 때, 내가 찾고자 하는 요소가 배열의 맨 첫 요소에 있는 상황

T(n) = 1

2) n개 요소를 가진 배열이 인풋으로 주어졌을 때, 내가 찾고자 하는 요소가 배열의 맨 뒷 요소에 있는 상황

T(n) = n

이처럼, 같은 크기의 인풋을 가짐에도 불구하고, 입력값의 상황에 따라 연산을 수행하는 횟수에는 차이가 있을 수 있다. 이대 최악의 시간 복잡도를 가지는 순간은 2번으로, Tw(n) = n 이라고 분석할 수 있다. 

이를 조금 더 일반화하여 최악의 경우 시간 복잡도 함수를 만들면 다음과 같이 쓸 수 있다. 

Tw(n) = max {t(I)| I 는 Dn 의 요소 중 하나}

여기서 Dn 은 인풋의 크기가 n 인 모든 가능한 입력의 집합이며, t(I) 는 그러한 D 에서 하나의 경우 걸리는 시간(선택된 연산자의 시행 횟수)이다. 따라서 Tw(n)은 곧 알고리즘을 수행하는 시간의 상한선이라고 할 수 있다. 

시간 복잡도 - 평균의 시간 복잡도 (Average - case time complexity)

이 시간복잡도의 경우, 최악의 시간 복잡도보다는 훨씬 적게 쓰인다. 이 시간 복잡도가 필요한 경우는, worst time complexity 가 지나치게 비관적으로 수행 시간을 분석하는 경우이다. 

평균의 시간 복잡도를 구하는 방법은 간단한데, 주어질 수 있는 모든 입력 경우에 대하여 확률을 곱한 뒤 그 전체 합을 구하면 그것이 바로 A(t) 가 된다. 이를 위해 각 인풋이 발생할 확률을 정의하는 것이 중요하다. 만약 확률을 정확히 구할 수 없는 경우라면, 데이터를 사용하거나 모든 입력이 똑같은 확률로 발생한다고 가정할 수도 있으나, 이 경우 정확한 값을 구하지 못하므로 불합리하다.

---

예시를 통해 W(n) 과 A(n) 에 대해 알아보도록 하자. 

def search(arr, x):
	for index, value in enumerate(arr):
    	if value == x:
        	return index 
    return -1 
 if __name__ == '__main__':
 	arr = [1, 10, 30, 15]
    x = 30
    
    #Function call 
    print(x, "is present at index", search(arr,x))

이 경우 W(n) 과 A(n) 은 각각 무엇일까? 

먼저 W(n) 부터 생각해 보자. 길이가 n 인 배열이 주어졌을 때, 내가 찾고자 하는 요소가 배열의 맨 뒤에 있는 경우가 가능한 모든 입력 경우 중 가장 많은 시간이 소요되는 최악의 경우일 것이다. 즉 n 번의 수행이 필요하므로 시간 복잡도는 T(n)임을 어렵지 않게 생각할 수 있다. 

다음으로 A(n)에 대해 살펴보자. 가능한 모든 입력 케이스에 대해서 내가 원하는 요소가 특정 자리에 오게 될 확률은 1/(n+1) 으로 같다. (여기서 n 이 아니라 n+1 이 온 이유는, 찾는 값이 배열에서 없는 경우도 고려해야 하기 때문이다.) 이를 곱해줄 경우, 1/n * (1부터 n 까지의 합 + n(찾는 값이 없는 경우)) 이 되며 이를 수식으로 나타내면, 전체 연산의 수 / 전체 경우의 수 이므로, { n(n+1)/2 + n } / (n+1) 가 된다. 이 경우 값은 거의 n/2 와 비슷해지고, 이를 O 표기법으로 나타내면, O(n) 임을 알 수 있다.

---

시간 복잡도 - 할부 상환 시간 복잡도 (Amortized time complexity)

앞서 살펴본 W(n) 과 A(n) 의 경우 각각 너무 비관적이다, 확률 값을 정확히 알지 못할 경우 정확도가 떨어진다는 문제점이 있었다. 이를 보완하기 위해 나온 시간 분석 방법이 바로 할부 상환 시간 복잡도이다. 할부 상환 분석의 기본 컨셉은 다음과 같다. 

더 많은 연산이 일어나는 연산자에게 더 비싼 값을 치르게 함으로써, 평균에 가까운 수행 결과를 분석한다. 

수업을 들을 때도 가장 이해하기 힘들었고, 지금도 제대로 이해했는지 의문이 가는 분석법이나, 나름대로 이해하고 다듬은 생각을 적어보려 한다. 사실 이 분석방법은 사용하기 어려워 많은 교수님들께서 언급만 하시고 지나가시는 것 같다. 

 

먼저 아래 예시를 W(n)으로 분석해 보자. 

multipop(k) 
push 
while not stack-empty and k =/= 0
	do pop 
    k <- k-1

"선택된 기본 연산자는" push, pop 으로 하고, 각각의 연산을 처리하는 데 O(1) 의 시간이 걸린다고 가정하자. 

위에서 정의된 함수 multipop(k)은 pop 을 k 번 시행하는 함수이다. 이 경우 최악의 시간 복잡도는 몇인가? 먼저 push의 경우 초기 값 설정을 위해 한 번만 정의되므로, O(1) 의 시간이 걸린다. 총 n 개의 요소가 저장된 스택이라면, min(n,k) 만큼 pop을 수행하게 될 것이며, 최악의 경우 시간 복잡도는 O(n)이다. 그러나 이는 pop 에서 주로 수행하는 기능의 시간 복잡도와는 괴리가 있다. 이제 이 괴리를 두 가지 할부상환 방식을 이용해 좁혀 보자. 

 

할부 상환 분석 - accounting method

첫 번째 방식은 accounting 방법이다. 직역하면, 계좌를 사용하겠다는 것인데, 위 알고리즘에서 push 를 할 때는 2$가, pop 을 할 때는 1$가 든다고 가정해 보자. 그럼, 연속적으로 일어남으로써, 반복해서 수행될 가능성이 높은 Pop 을 아무리 많이 재생해도, pop 은 무료로 수행이 가능하기 때문에, 돈이 들지 않는다. 즉 accounting 방법이란 연산이 여러 개 있을 때, 그 연산의 총합만 같다면, 반복되는 연산에는 낮은 값을 주고, 그 만큼 아낀 돈을 별로 쓰이지 않는 연산에 줌으로써, 평균과 최대한 가깝게 시간 복잡도를 구하는 방법이라고 보면 된다. 과연 이렇게 했을 때, 문제가 발생하진 않을지 검증해 보도록 하자. 

Push 4번 pop push push multipop4 의 순으로 연산이 일어났다고 가정해 보자.

[a], [a,b], [a,b,c], [a,b,c,d], [a,b,c], [a,b,c,e], [a,b,c,e,f], [a]

기존의 방식대로, 모든 연산에 동일한 비용을 준다고 하면, 1 1 1 1 1 1 1 4, 총 11$가 들어가게 된다. 

이번엔 accounting method 를 적용해 보도록 하자. 2 2 2 2 0 2 2 0, 총 12$가 들어가게 된다. 

->> 이 경우는 같지 않은데...??? 증명 실패..

 

이처럼 할부 상환 분석은, 가상의 계좌가 있다고 가정한 뒤에 기준보다 더 높게 측정한 연산을 수행할 때는 계좌에서 부족한 돈을 끌어와 사용하고, 기준보다 더 낮게 측정한 연산을 수행할 때는 사용하고 남은 돈을 계좌에 저축함으로써 연산 하나당 걸리는 평균적인 시간을 구할 수 있게 된다. 위 경우, 총 12$의 연산이 8번에 걸쳐 나타났으므로, 연산 하나에 쓰인 돈은 12/8 = 1.5$ 라고 볼 수 있다. 그리고 이렇게 구해진 연산의 평균 시간 복잡도는 amortized cost 라고 불린다. (평균비용)

->> 사실 이 amortized 부분은 강의에서 깊게 다루지도 않았고, 책에서의 정리도 빈약해 이해가 깊지 않다. 따라서 부정확한 정보가 포함될 수 있으니 주의하시길..

 

할부 상환 분석 - potential method

할부 상환 분석의 두 번째 방법은 potential method이다.

potential energy 는 사실 위치 에너지이다. 중학교 과학 시간에 나오는 개념인데, 여기서 과학적인 내용까지 알 필요는 없고, 그냥 물체가 어떤 위치에 놓여있음으로써 가지게 되는 에너지라고 이해하면 된다.  

우리는 이제 이 위치 에너지가 자료 구조에도 있다고 가정할 것이다. 어떤 자료구조에 위치 에너지를 주는 함수를 P(d) 라고 정의하자. 앞선 accounting method 방식이 가상의 계좌를 설정하고, 계좌의 돈을 사용했다면, 이제는 이 위치 에너지를 계좌 대신에 사용할 것이다. 

 

어떤 연산 op1 이 자료구조 D1 을 D2 라는 자료구조로 바꾼다고 가정하자. 이때, op1 의 평균 수행 비용은 P(D1) - P(D2) + realcost(op1) 이다. 즉 바꾼 자료구조의 에너지에서 바꾸기 전 자료구조의 에너지를 빼면, 해당 연산이 영향을 미친 에너지의 양을 구할 수 있으며, 해당 연산을 수행하는 데에도 에너지가 필요하므로, 이를 더하면 위 식을 얻을 수 있다. 

 

이제 스택의 예를 들며 amortized time complexity 를 potential method 로 구해보자. 어떤 자료구조 D 가 가지는 Potential energy 는 스택의 길이라고 가정한다. 

Amortized cost 는 어떤 연산을 사용하는 데 드는 실제 비용과, 그것의 potential 에너지를 합한 값으로 정의되는데, 스택에서는 Push 와 pop 이 주요 연산이므로, 이 둘의 amortized cost 를 먼저 분석하면 다음과 같이 나타낼 수 있다. 

 

push 의 amortized cost 

push 의 real cost = 1 (push 라는 연산 자체를 하는 데 필요한 비용)

push 의 potential 도 1 (push 를 하게 되면 스택의 길이가 1만큼 증가하기 때문에)

Amortized cost 는 1+1 로 2이며 이를 빅오 표기법으로 나타내면 O(1) 

 

pop 의 amortized cost 

pop 의 real cost = 1 (pop 이라는 연산 자체를 하는 데 필요한 비용)

pop 의 potentia 은 - 1 (pop 을 하게 되면 스택의 길이가 1 감소하기 때문에)

Amortized cost 는 1-1 로 0 이며 이를 빅오 표기법으로 나타내면 O(1) 

 

앞서 살펴 보았던 accounting method 와 결과적으로는 같다는 것이 보일 것이다. push 의 amortized 는 2 pop 의 amortized 는 0 이다. 다만 앞서 살펴보았던 accounting method 에서는, 애초에 2 와 0 이라는 가상의 값을 부여한 뒤에, 부족한 돈/ 남은 돈을 계좌에서 관리하는 방식이었고, 이 방법의 경우 어떤 연산을 수행 한 후의 결과를 바탕으로 에너지를 측정했다는 데에서 차이가 있다. 

 

다음으로 multipop 의 amortized cost 를 구해보자. 

multipop 을 수행하는 데 필요한 real cost 는 min(k, s) 이다. 한편 potential 은 -min(k,s) 이다. 따라서 amortized cost 는 이 둘의 합인 0 이며 이는 곧 O(1) 으로 표현될 수 있다. 

 

여기까지의 결과를 종합해 분석햇을 때, pop, push, multipop 의 시간 복잡도는 모두 O(1) 으로 같다라는 것을 알 수 있다. 

->> 거듭 말하지만, 이 amortized time complexity 에는 틀린 내용이 다수 포함되어 있을 수 있다. 

---

공간 복잡도

지금까지는 연산의 횟수와 관련된 시간 복잡도에 대해서 알아봤다면 지금부터는 메모리에 관한 이야기로 넘어가게 된다. 알고리즘을 수행하기 위해서는 명령어, 변수, 상수, 인풋 데이터 등을 메모리에 저장해야 한다. 이때 메모리 공간을 적게 쓸수록 효율적인 알고리즘이라 할 수 있다. 공간 복잡도에도 시간 복잡도와 마찬가지로 최악의 경우 분석법과 평균 분석법이 있다. 

---

최적성

어떤 문제를 해결하기 위해 알고리즘을 작성할 때, 알고리즘이 반드시 수행해야 하는 최소한의 연산이 있을 것이다. 어떤 수를 써도 더이상 줄여지지 않는 상태. 그 상태를 그 문제의 하한선이라고 한다. 그리고 이 하한선에 위치한 알고리즘을 최적 알고리즘이라고 부른다. 즉 가능한 모든 알고리즘 중에서 더 이상 줄일 수 없는, 가장 효율적인 상태의 알고리즘. 이는 알려진 알고리즘 중에서 가장 좋다는 말과 분리할 필요가 있다. 알려지지 않은 알고리즘 중에 알려진 알고리즘보다 개선될 여지가 있는 알고리즘이 있다면, 알려진 알고리즘 중에 가장 빠른 알고리즘은 최적 알고리즘이라고 할 수 없다. 

 

그렇다면, 어떤 알고리즘이 최적 알고리즘이라는 것은 어떻게 알아낼 수 있을까? 간단하게도, 그 알고리즘의 시간 복잡도가 이론적인 Lower bound 와 같은지를 증명하면 된다. 이때 시간 복잡도로는 주로 W(n) 이 사용된다. (A(n)도 사용될 수 있다.) 

만약 L(n) < W(n) 이라면, 해당 알고리즘이 최적 알고리즘이 아니거나, L(n) 의 경계가 더 낮은 것인데 아직 연구되지 않은 것일 수도 있다. 

 

이제 예시를 통해 알고리즘의 optimality 를 판단해 보자. 

For i from 1 to n:
	For j from 1 to p:
    	sum = 0
        For k from 1 to m:
        	Set sum <- sum + Aik*Bk 
        Set Cij <- sum 
Return C

위 알고리즘은 N*N 행렬의 곱셈을 수행하는 코드이다. 위 코드에서 W(n)은 n^3 이며 Lowerbound 는 n^2 으로, 위 알고리즘은최적 알고리즘이라고 할 수 없다. 실제로 이보다 더 좋은 알고리즘들이 존재한다. 

다만 최적 알고리즘을 구하기 위해 필요한 L(n) 의 경우 숱한 연구와 증명이 수반되어야 하는 것이기에, 알고리즘의 최적성을 판단하는 것은 쉬운 일이 아니다. 

---

차수 표기법

시간 복잡도를 계산할 때, 우리는 모든 연산의 시행 횟수를 고려하지 않았다. 총 연산의 수에 비례해서 증가하는 연산을 찾고, 해당 연산의 반복 횟수를 시간 복잡도라 정의했다. 마찬가지로 시간 복잡도를 다항식으로 나타냈을 때, n 이 커질수록 시간 복잡도는 차수가 높은 항에 비례할 것이며 상수가 끼치는 영향은 미미할 것이다. 이러한 관점에서 우리는 시간 복잡도를 다시 한 번 간추를 수 있으며, 이를 가능케 하는 것이 차수 표기법이다. 다시 말해, 차수 표기법이란 계수 및 차수가 작은 항들을 무시하고 복잡도 함수를 정의하는 방법이다.

 

차수 표기법은 3가지로 나눌 수 있다.

1. Big O 표기법 (상한선)
2. Omega 표기법 (하한선)
3. Theata 표기법

Big O 표기법

T(n) 의 시간 복잡도를 가진 알고리즘이 있다고 할 때, 이를 f(n) 으로 나누고 n 을 양의 무한대로 발산시켰을 때 나오는 극한값이 0이상의 상수라면 f(n) 은 T(n) 의 상한선이라 말할 수 있다. 이 말인 즉슨, f(n) 에 어떠한 상수를 곱해도 T(n) 보다 커지지 않는다는 것이기 때문이다.

Omega 표기법

Big O 표기법과 반대되는 표기법으로, 시간 복잡도의 하한선을 뜻한다. 다시 말해, 위 수식의 결과가 양의 무한대로 발산하거나 k 가 0보다 큰 상수로 수렴한다면 f(n) 은 T(n) 의 하한선이라 볼 수 있다. 

Theata 표기법 

한 알고리즘의 Big O 표기법과 Omega 표기법 사이에 위치해 있다면, 그 알고리즘의 시간 복잡도를 보다 정확히 표현할 수 있게 되며, 이를 Theata 표기법이라 한다. 

---

알고리즘 효율성 비교하기

지금까지 배운 내용을 바탕으로 알고리즘의 효율성을 한 번 비교해 보자. 

하나의 알고리즘을 다른 알고리즘으로 나눈 뒤 극한값이 0이라면 분자 알고리즘이 더 효율적이며 발산한다면 분모 알고리즘이 더 효율적이다. 그런데 만약, 루트 n 과 log2n 처럼 직관적으로 극한값을 구할 수 없는 상황이라면, 로피탈의 정리를 활용하여 극한값을 구하는 방향으로 수식을 전개시킬 필요가 있다.