Complexity Analysis

알고리즘의 correctness가 증명되었다면, 다음은 performance 확인이 필요하다. Performance 확인에는 complexity 분석이 진행된다.

Complexity Analysis

Complexity에는 2가지 종류가 있다.

• A complexity of an algorithm
  • Time complexity
  • Space complexity
• A complexity of a problem

Problem의 complexity는 쉽게 말해 optimal한 solution이 가지는 complexity를 의미한다.

알고리즘의 complexity는 Time과 Space 영역으로 나뉘게 된다. 그 이유는 현대의 컴퓨터 구조(폰 노이만 구조)가 연산장치와 저장장치로 나뉘었기 때문이다. 보통 Time complexity를 우선적으로 검토하는데, 그 이유는 저장장치보다 연산장치가 비싸기 때문이다.

또한 Time complexity와 Space complexity는 어느정도 trade-off 관계에 있다. Time complexity를 줄이기 위해 많은 양의 cache를 사용할 수 있고, Space complexity를 줄이기 위해 단일 cache만을 사용해 동작할 수 있기 때문이다.

How to measure complexity?

Complexity를 측정하는 가장 쉬운 방법은 실제로 스탑워치를 이용해 알고리즘의 시작과 끝 시간을 측정하는 방법이다. 그러나 이 방법에는 문제가 있다.

알고리즘의 퍼포먼스는 알고리즘이 수행되는 기계나 OS 그리고 Input에 의해 결정될 수 있다. 좋은 기계라면 알고리즘이 빠르게 수행될 수 있고, Interrupt이 많은 OS에서 수행된다면 느려질 수 있고, Input 양이 많다면 느려질 수 있기 때문이다.

그러므로 실제로는 기계, OS, Input 양의 영향을 제거하기 위해 동일 Input(size=n)에 대한 알고리즘의 계산량(계산 명령어의 수)을 통해서 퍼포먼스를 측정한다. 앞서 살펴보았던 알고리즘을 통해 Time complexity를 구해보자.

Problem : set A에서 largest number 찾기
Algorithm(A[1...n])
 1.    For i = 1 to n
 2.        ln = A[i]
 3.        flag = True
 4.
 5.        For j = 1 to n
 6.        	if A[j] > ln then,
 7.            flag = False
 8.        end For
 9.
10.        if flag == True then,
11.            output = ln
12.    end For
13.    return output

중요한 가정이 하나 추가된다. 바로 Operation의 수행시간은 unit time이라는 가정이다. 실제로는 '+' 계산의 수행시간과 '/' 계산의 수행시간에 차이가 있지만, 알고리즘의 시간 복잡도를 계산하는 부분에서는 의미가 크지 않기 때문에 unit time으로 가정하여 사용한다.

1. $C_{i}$를 바깥 for문 한 번 도는데 걸리는 계산량이라고 하자.
2. 그러면 알고리즘의 시간 복잡도는 다음과 같다.
   $T(n) = \sum_{i=1}^{n}C_{i} + 1$
3. 그리고 $C_{j}$를 내부 for문의 계산량이라고 하자. 그러면 $C_{i}$는 다음과 같다.
   $C_{i}=2+C_{j}(+1)$
4. $C_{j}$는 조건문이 수행되는 정도에 따라 범위가 정해진다. 모든 iteration에 수행되는 경우 2n, 한번도 수행되지 않는다면 n의 값을 가질 수 있다.
   $n<C_{j}<2n$
5. $C_{i}$의 범위도 정해진다.
   $n+2<C_{i}<2n+3$
6. 따라서 알고리즘의 시간복잡도를 구할 수 있다.
   $n^{2}+4n+5 < T(n) < 4n^{2}+12n+10$

Function Growth Rate

앞선 복잡도 분석에서 n이 만약 무한정으로 커진다면 어떻게 해야 할까? 이를 판단하기 위하여 알고리즘의 시간 복잡도를 함수로 분석한다.

Asymptotic Function Growth

시간 복잡도를 정의하기 위해 몇가지 정의가 사용된다.

Upper Bound

• $O$ notation
  $n>n_{0}$에 대하여 $f(n) \leq cg(n)$을 만족하는 양수 $c, n_{0}$이 존재하면 $f(n)=O(g(n))$이라고 한다.

• $o$ notation
  $n>n_{0}$과 모든 양의 수 $c$에 대하여 $f(n) \leq cg(n)$을 만족하는 양수 $n_{0}$이 존재하면 $f(n)=o(g(n))$이라고 한다.

Lower Bound

• $\Omega$ notation
  $n>n_{0}$에 대하여 $f(n) \geq cg(n)$을 만족하는 양수 $c, n_{0}$이 존재하면 $f(n)=\Omega (g(n))$이라고 한다.

• $\omega$ notation
  $n>n_{0}$과 모든 양의 수 $c$에 대하여 $f(n) \geq cg(n)$을 만족하는 양수 $n_{0}$이 존재하면 $f(n)=\omega (g(n))$이라고 한다.

Tight Bound

• $\Theta$ notation
  $n>n_{0}$에 대해서, $f(n) \geq c_{1}g(n)$과 $f(n) \leq c_{2}g(n)$을 만족하는 양의 정수 $c_{1}, c_{2}, n_{0}$가 존재하면 $f(n)=\Theta(g(n))$이라고 한다.