#6 [C 자료구조] 알고리즘 성능의 척도: 시간 복잡도의 계산법

알고리즘 성능은 보통 공간보다 시간 복잡도의 측면에서 고려된다.

따라서 우리는 시간 복잡도를 계산하는 방법을 더 자세하게 배우고 배워야 한다!! 실제로 알고리즘 대회에서 가장 많이 쓰인다.

 

후 우리는 이 겁나 복잡한 알고리즘이 몇 억겁의 시간에 걸쳐서 구현해내는지 계산해야한다.

구현 방법은 어렵지만 성능 계산은 어렵지 않다!!라고 믿고 가즈아

1. COUNT 변수를 이용한 

1) 반복문 (terative) 계산

반복문은 프로그램 단계별로 단순히 count++를 넣어줌으로써 이 LOOP가 몇 번 돌아가는지 알아낼 수 있다.

다음과 같은 코드를 보자

 

float sum(float list[ ], int n) {
    float tempsum = 0; count++; //sum 함수를 전체 한번 돌리는 거니까 여기서 +1
    int i;
    for ( i=0; i<n; i++ ) {
        count++; //여기 for문이 몇 번 도는지 체크하기 위한 것 +n
        tempsum += list[i]; count ++; //더하기 연산을 했으니 +n
    }
    count++; //for문이 끝났다는 것을 알려주는 +1
    count++; //return하기 위한 +1
    return tempsum;

따라서 Total Count = 2n + 3

각각의 count ++는 프로그램의 act를 기반으로 한 것이다.

여기까지는 어렵지 않쥬?

 

2) 회귀 함수(Recursive) 계산

회귀 함수는 자기 자신(i.e. n-1의 자신)을 호출하는 함수라는 것을 알고 있을 것이다!

따라서 이것 또한 1)과 다르지 않게 어렵지 않다.

 

float rsum(float list[ ], int n) {
    count++; //자 함수 들어간다 입 벌려!! <+1> n=0이 나올때까지 회귀! <+n>
    if (n) {
        count++;
        return rsum(list, n-1) + list[n-1];  //예전의 나를 호출하는 과정 +n

    }
    count++; //return하기 위한 +1
    return list[0];
}

따라서 Total Count = 2n + 2

이 것도 어렵지 않쥬?

 

3) 행렬(Matrix) 계산

행렬은 말그대로 for문 중첩이라고 생각하면 된다. 제일 안쪽의 for문은 2개면 x*y, 3개의 x*y*z번 돌게 될 것이다. 루프에 의해 살짝은 복잡해 보일 수 있지만 원리는 간단하다.

 

void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE], int row, int cols) {
    int i, j;
    for ( i=0; i < rows; i++ ){
        count++; //i 루프를 위한 카운트 +row
        for ( j=0; j<cols; j++ ){
            count++; //j 루프를 위한 카운트 +(row*col)
            c[i][j] = a[i][j] + b[i][j];
            count++; //드디어 본 식 계산을 위한 카운트 +(row*col)
        }
        count++; //j 루프 끝났음을 알려주는 +row
    }
    count++; //i 루프 끝났음을 알려주는 +1
}

따라서 Total Count = 2*row*col + 2*row + 1

여기선 return을 따로 안써서 return에 의한 카운트는 없다.

중복 for문 같은 경우 다음과 같이 계산해주면 된다.

2. 

count와 같은 값을 출력하기 위한 것이지만 방법론만 다른 것이다.

조금 더 인간의 입장에서 접근했다고 보면 된다. 예시로 방금 실행했던 3) 행렬 계산을 보도록 해보자.

s/e = Steps/Execution

여기서 우리는 Total Count = 2*row*col + 2*row + 1 이라는 동일한 값을 얻을 수 있다. count++ 대신 인간이 직접 각 항목에서 몇 번씩 계산되는지 세는 것이다.

 

예쓰!!! 튜토리얼을 완료했다. 이제 알고리즘 복잡도를 표현하는 본격적인 항해를 시작해보자 ^3^ 아이 즐거워