[알고리즘] 알고리즘 분석, Analysis | 최선, 최악, 평균, 모든 경우

  알고리즘을 짰다고해서 끝나는 것이 아니다. 짜긴 짰는데 결과 값을 얻어내기까지 어마어마한 시간을 요구한다면 소용이 없기 때문이다. 따라서 분석을 통해 알고리즘의 효율성을 판단해야한다. 알고리즘의 성능은 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 표현한다.

시간복잡도: 얼마나 빠른가? 
공간복잡도: 얼마나 많은 공간을 차지하는가?

 

우선, 시간 복잡도 측정에 대해 주로 다뤄보도록 하겠다. (공간 복잡도는 나중에 중간중간 나올 예정)

 

---

시간복잡도

  시간복잡도(Time Complexity)는 알고리즘이 '얼마나 빠른가'를 나타내는 함수이며, 보통 함수 이름으로 T(n)을 사용한다. 즉, n과 T(n)의 관계를 구하는 것인데, 이 때 n은 input size가 된다. 시간 복잡도의 표현 척도는 다음과 같다.

 

표현 척도
- input size (=입력크기, n)
- basic operation (=단위연산)

 

  이 때, basic operation은 코드에서 비교, 지정 등의 부분이 될 수 있다.

ex) result = result + S[ i ]; 혹은 if (S[ j ] < S[ i ])

 

  이런 개념들은 나중에 코드에 직접 대입해서 보는게 이해하는데에 더 도움될 것 같다.

 

---

분석 방법

 분석 방법으로는 Every-case, Worst-case, Average-case, Best-case 등이 있다. 하나하나 알아보자.

 

▷Every-case, 모든경우, T(n)

  경우가 나뉘어지지 않고, 한 가지 경우만 존재한다. 입력크기 n에만 종속할 뿐, 입력 값(내용)과는 무관하게 결과가 항상 일정하다. 아래의 배열 내의 숫자를 모두 더하는 단순 알고리즘을 통해 알아보자.

 

//배열 값을 더하는 알고리즘

number sum(int n, const number s[]){
  index i;
  number result;
  
  result=0;
  for(i=1; i<=n; i++)
    result = result + s[i]; //basic operation
    return result;
  }

 

  result = result + s[ i ]; 이 부분을 basic operation으로 할 때, 배열 내용에 상관 없이 for 루프가 n번 반복되므로, basic operation도 배열 내용에 상관 없이 n번 수행된다. 따라서 위의 알고리즘의 경우 T(n)=n으로, every-case이다.

 

▷Worst-case, 최악의 경우, W(n)

  경우가 나눠지고, 그 중 최악의 경우를 의미한다. 이 때 최악이라는 것은 단위 연산이 수행되는 횟수가 최대라는 것이다. 입력 크기와 입력 값(내용) 모두에 종속된다. Worst-case의 예는 아래 Best-case에서 함께 설명하겠다.

 

▷Best-case, 최선의 경우, B(n)

  Best-case는 Worst-case의 반대라고 생각하면 된다. 연산 수행 횟수가 최소인 경우이다. 아래의 교환 정렬 알고리즘을 통해 알아보자.

 

//교환 정렬 알고리즘, exchange sort

void exchangesort(int n, keytype s[]) {
  index i, j;
  
  for(i=1; i<=n-1;i++)
    for(j=i+1; j<=n; j++)
      if(s[j] < s[i]) // 1
        exchange s[i] and s[j]; // 2
 }

 

위 코드를 통해 Worst-case를 알아보기 전에 한 가지 알아둬야 할 것은, 코드 상에서 '어떤 부분을 basic operation으로 두냐에 따라 Every-case인지, Best/Worst-case인지의 여부가 달라진다' 라는 것이다.

  먼저, exchange s[ i ] and s[ j ]; (주석 2) 이 부분을 basic operation으로 할 때를 알아보자. 이 경우에는 위의 조건문의 결과에 따라 exchange를 할 수도 있고, 안할 수도 있으므로 best-case와 worst-case가 존재한다. 즉, every-case가 아니다. 반면, if(s[ i ] < s[ i ]) (주석 1) 의 이 조건문을 basic operation으로 할 경우, 모든 횟수에 한번씩 반드시 거치므로 every-case이다.

 

① if(s[ i ] < s[ i ]) 가 basic operation일 때

i	연산 횟수
1	n - 1
2	n - 2
3	n - 3
.   .   .
n - 1	1

연산 횟수 합 : 1 + 2 + 3 + ... n -1 = n(n - 1) / 2

즉, basic operation이 n(n - 1)/2번 수행된다.

 

② exchange s[ i ] and s[ j ]; 가 basic operation일 때

최악의 경우에는 exchange가 매번 일어나게 되는 것이고, 따라서 basic operation인 exchange가 n(n - 1)/2번 일어난다.

 

최선의 경우, 즉 처음부터 정렬이 되어있는 경우에는 exchange가 일어나지 않으므로 B(n)=0이다.

∴ B(n) = 0

 

▷Average-case, 평균의 경우, A(n)

  모든 경우를 분석해서 그 평균을 낸 것이다. 이 때 입력 크기와 입력 값(내용) 모두에 종속한다. 만약 Every-case인 알고리즘을 갖고 Average-case를 구한다면 당연히도 Every-case와 Average-case의 값이 갖게 나올 것이다. Average-case는 확률을 바탕으로 계산된다. Average-case의 예는 아래 순차검색에서 다같이 다룰 것이다.

 

---

적용 예제

  마지막으로 순차검색(sequential search)를 사용하여 앞서 알아본 Every-case, Worst-case, Best-case, Average-case를 모두 적용해보자.

 

//순차 검색, sequential search

void seqsearch(int n, const keytype s[], keytype x, index location) {
  location = 1;
  while(location <=n && s[location]!=x) //basic operation
    location++;
  if(location > n)
    location=0;
}

 

  basic operation이 s[ location ] != x 라고 치자. (이렇듯 알고리즘을 분석하기 위해서는 basic operation이 어느부분인지 항상 결정되어있어야한다!)

  이 알고리즘은 every-case일까? 아니면 best/worst-case일까? 위 알고리즘은 '검색' 알고리즘이고, 배열 내의 원소들 중에서 특정 값을 찾아내는 것이다. 따라서, 배열 내에 어떤 내용이 있느냐에 따라 검색하는 횟수가 달라지므로 모든 경우분석은 불가능하다. 즉, 이 알고리즘은 best/worst-case 알고리즘이다. 그렇다면 best-case, worst-case를 알아보자.

 

1) Best-case

  s[ location ] != x 은 배열 내 원소가 찾고자 하는 키 x인지 확인하는 부분인데, best-case, 즉 값을 한번에 찾는다면 이 부분은 몇번 실행될까? 그렇다.(대답도 안듣고 말하기) 1번 실행된다. ㅋㅋ 따라서 B(n)=1이다.

  ∴ B(n) = 1

 

2) Worst-case

  worst-case는 언제일까? 찾고자하는 값이 배열의 맨 끝에 있거나 아예 배열 내에 없을 때이다. 이 경우 basic operation은 배열의 크기만큼, 즉 n번 실행된다.

  ∴ W(n) = n

 

3) Average-case

  average-case는 x가 배열 내에 있을 확률과 없을 확률을 바탕으로 계산이 이루어진다. 먼저 있을 확률과 없을 확률을 다음과 같이 설정해둔다.

  있을 확률 : p , 없을 확률 : 1 - p

① x가 배열 s에 무조건 있다.

  1≤k≤n에 대해 x가 k번째에 있을 확률 :

  x가 k번째에 있을 때 s를 찾기위해 수행하는 단위연산 횟수 : k

 

② x가 배열 s에 없을 수도 있다.

  k 번째에 있을 확률 : p/n

(이 p에 확률을 적용하면 값을 얻어낼 수 있다.)

 

 

---

  알고리즘 수업을 듣다보면 꼭 T(n)은 뭐고 .. W(n)은 뭐고.. 이런 말들이 많이 나오기 때문에 미리 개념을 확실히 잡아두는게 좋다.. 필자는 수업을 열심히 듣지않아 T가 뭐고 W가 뭐고 A는 또 뭔지.. 몰랐기 때문...

 

  다음시간엔 order에 대해 알아보도록 하겠다! 블로그에 시그마를 쓰려면 html문서 형식으로 작성해야한다는 것을 처음 알았고........ 수식 적는데 시간 엄청 잡아먹혔다 ㅋㅋ LaTex를 쓰라나 뭐라나... 

이제 배그해야겠다