알고리즘의 성능 분석 방법

알고리즘의 성능을 분석하는 방법은 뭘까?

 

알고리즘의 runtime이 짧으면 좋은 성능인 것일까?

 

이 running time을 측정하는 방법은 프로그램을 수행하는 기기에 의존적일 수 밖에 없다.

간단하게 연산이 빠른 슈퍼컴퓨터와 일반 컴퓨터로 동일한 프로그램을 실행하면 일반적으로 슈퍼컴퓨터가 빠를수밖에 없기 때문이다.

 

우리는 컴퓨터의 성능을 측정하는 것이 아닌 알고리즘의 성능을 분석하는 것이기 때문에

알고리즘에서는 특별한 성능 측정 방법을 사용한다.

 

복잡도 Complexity

1. 공간 복잡도 (Space Complexity)

이 문제를 해결하는데 얼마만큼의 메모리가 필요한가?

고정된 필요 메모리와 가변 메모리 요소의 합으로 나타낸다.

2. 시간 복잡도 (Time Complexity)

이 문제를 해결하는데 얼마만큼의 시간이 필요한가?

여기서의 시간은 실세계의 물리적인 시간이 아니다 (시간복잡도의 단위는 초가 아니다)

 

 

 

알고리즘 분석에서 복잡도를 이야기할땐 보통은 공간복잡도 보다 시간 복잡도를 이야기한다.

보통 알고리즘이 차지하는 공간보다는 수행시간에 더 관심이 있기 때문이다.

 

위에서 말한 것처럼 시간 복잡도의 시간은 실세계의 물리적인 시간이 아니라고 했다.

시간 복잡도에선 알고리즘의 실행시간이 아닌 프로세스가 수행하는 연산의 개수를 숫자로 표시하게 된다. 여기서 각각의 연산에 걸리는 시간은 분석에서 고려하지 않는다.

 

 

사실 위에서는 연산의 횟수라 했지만 실행되는 문장의 수를 세도 시간복잡도를 분석하는데는 큰 영향이 없다.

 

다음의 sum함수를 보자

float sum(float list[], int n) {
    float tempsum;
    int i;
    tempsum = 0;
    for (i =0; i<n; i++){
        tempsum += list[i];
    }
    return tempsum;
}

다음 함수에선 몇개의 문장이 수행될까?

물론 세는 기준에 따라서 조금씩 달라질 수 있겠지만 최종적인 결론에는 지장이 없으니 세어보자

tempsum = 0; // 1
    for (i=0; i<n; i++) // n+1
        tempsum += list[i]; // n
    return tempsum; //1

나는 선언부를 제외하고 총 2n+3으로 세었다. 조금 다르게 세더라도 상관없다.

1차식으로만 나왔다면 모두 괜찮다!

 

 

다음의 arrayMax함수도 수행 개수를 세보자

float arrayMax(float A[], int n){
    float max;
    int i;
    max = A[0];
    for(i=1; i<n; i++){
        if (max < A[i]){
            max = A[i];
        }
    }
    return max;
}

이번에는 위의 sum함수와 다르게 반복문 안에 조건문이 들어있다.

	max = A[0]; // 1
    for(i=1; i<n; i++) // n
        if (max < A[i]) // n-1
            max = A[i]; // n-1
    return max; // 1

나는 3n-1로 세었다.

이번 함수는 조건문이 있어서 어떻게 세야 할지 고민이 된다.

하지만 우리가 분석할때는 보통 최대 얼마만큼 걸릴지를 원하기 때문에 모든 조건이 true가 되는 최악의 경우를 염두해 둔다.

이번에도 마찬가지로 조금 다르게 세더라도 상관없다.

1차식으로만 나왔다면 모두 결론에는 지장이 없다.

 

마지막으로 다음 add함수의 수행 개수를 세보자

void add(int a[][M_SIZE] ... , int n){
    int i,j;
    for(i=0;i<n;i++){
        for(j=0; j<n; j++){
            c[i][j] = a[i][j] + b[i][j];
        }
    }
}

 반복문 안에 반복문이 들어있는 이중반복문이 들어있다.

 

void add(int a[][M_SIZE] ... , int n){
    int i,j;
    for(i=0;i<n;i++){ // n+1번
        for(j=0; j<n; j++){ // n*n+1번
            c[i][j] = a[i][j] + b[i][j]; // n²번
        }
    }
}

나는 2n²+2n+1로 세었다.

이번에는 2차식으로 세었다면 결론에는 지장이 없다.

 

다음의 그래프를 봐보자

우리가 문장 실행 횟수를 세봤던 첫번째 sum함수와 두번째 arrayMax함수는 1차식으로 알고리즘 B에 해당하고

 

세번째로 세봤던 add함수는 2차식이기 때문에 알고리즘 C에 해당한다.

 

알고리즘 A는 반복문이 없는 input과 상관 없이 동일한 문장 실행 개수를 가지고 있는 알고리즘에 해당한다.

 

어떤 알고리즘이 좋다고 볼 수 있을까?

input size가 작을땐 연산량이 알고리즘 B, C보다 많은 A가 더 많은 것처럼 상황에 따라서 다르다고 할 수 도 있으나

통상적으로 복잡도를 구할땐 input size가 아~주 크다고 가정한다

그리고 우리는 n이 커질때 어떤 알고리즘이 더 좋은지에 관심이 있다!

 

그렇기에 알고리즘 C보다는 B가, B보다는 A가 좋다고 할 수 있다.

 

빅오 표기법

위에서 문장의 실행 횟수를 셀 때 왜 차수만 같으면 상관 없다고 했냐면 바로 이 시간복잡도를 표현하는 빅오 표기법 때문이다.

 

빅오 표기법의 정의는 이렇다.

빅오 표기법의 정의

정의에 너무 고민해보지 말고 예제를 보면 쉽게 이해가 될것이다.

 

3n+2 = O(n) 이걸 정의에 따라서 입증해 보면 3n+2 <= c*n 이 부등호를 만족시키는 c값이 존재하면 된다. n>=2, c=4  

 

3n+2 = O(n²) 이렇게 나타낼수도 있지만 바람직하진 않다. 빅오표기법은 상한을 표기한 것임으로 여러 값이 존재할 수 있지만 가능한 작은 값을 적어줘야 의미있는 분석이 된다.

 

 

또한 다음과 같은 시간 복잡도 함수를 가정해 보자 T(n) = n²+n+1

n이 1000이라면 각 항은 1000000+1000+1 으로 차수가 가장 큰 항이 전체의 값을 주도하게 된다.

그렇기 때문에 시간복잡도 함수에서도 가장 큰 항만을 고려하면 충분하다.

 

그래서 빅오 표기법으로 다음과 같은 복잡도 함수를 표현하면 이렇다.

n+5 = O(n)

2n+3 = O(n)

3n-1 = O(n)

2n²+2n+1 = O(n²)

 

 

통합해 볼때 간단하게 알고리즘에서 빅오를 계산하자면

 

그 알고리즘의 재귀와 반복문을 확인하면 된다.

 

또한 빅오는 가장 오래 걸릴 경우의 시간복잡도를 표현하는 방법이다.

 

 

 

 

 

O(1) : 상수개의 연산만 수행할때 

O(n) : 연산이 선형적으로 증가할때 ex) 단일 반복문

O(n²) : 반복문이 중첩되어 있을때

O(n³) :

O(2ⁿ) :