3. 알고리즘의 성능분석을 분석하자!

18 Jan 2017 . category: Data_Structure . Comments
#korean #theory #data_structure

알고리즘의 성능분석 방법

알고리즘을 성능적으로 분석해야할 일이 생긴다. 그렇기 위해서는 알고리즘을 분석도 해야하고 수학적으로 표현도 하고 계산도 해야한다. 수학을 못하는 나는 망했다. 이번 글에서는 알고리즘의 성능을 어떻게 분석하고 어떻게 수학적으로 표현할 지에 대해서 공부해보도록 하겠다.

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

우리는 공대생이므로 잘 동작하는 것 뿐만 아니라 성능이 좋은 알고리즘을 찾아야할 의무가 있다. 그러나, 세상에 모든 경우에 항상 우월한 성능을 보이는 알고리즘은 없다. 그러므로 우리는 두가지 요소를 고려해야한다.

• 어떤 알고리즘이 어떠한 상황에서 더 빠르고 더 느린가?
• 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰나?

첫 번째 것은 ‘속도’에 관한 것이다. 속도에 해당하는 알고리즘 수행시간 분석결과를 가리켜 시간 복잡도(Time Complexity) 라고 부른다.

두 번째 것은 ‘메모리의 사용량’에 관한 것이다. 이에 해당하는 분석결과를 가리켜 공간 복잡도(Space Complexity) 라고 부른다.

원론적으로는 둘다 좋아야 최적의 알고리즘이다. 하지만, 일반적으로는 실행속도에 초점 을 둔다. 알고리즘의 속도를 재는 방법은 다음과 같다.

• 연산의 횟수를 센다.
• 처리해야 할 데이터의 수 \(n\)에 대한 연산횟수의 함수 \(T(n)\)을 구성한다.

즉, 연산의 횟수가 많아지면 속도가 느려진다는 것이고, 고로 연산이 횟수가 적어야 빠른 알고리즘이다. \(n\)에 대한 연산횟수의 함수 \(T(n)\)을 구성함으로써 \(n\)에 따라 연산횟수의 변화정도를 알 수 있다. \(T(n)\)의 그래프를 이용해서 알고리즘의 수행속도를 쉽게 비교할 수 있다.

순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석의 핵심요소

시간 복잡도는 최악의 경우 를 가정해서 평가할 수 있다. C언어 코드로 순차탐색 알고리즘을 알아보자.

int LinearSearch(int inputArray[], int arrayLength, int target) {
    int i;
    for (i = 0; i < arrayLength; i++) {
        if(array[i] == target) {
            return i; // 찾은 대상의 인덱스 값 반환
        }
    }
    return -1; // 찾지 못함
}

위는 순차 탐색 알고리즘의 핵심코드이다. 순차 탐색은 말 그대로 배열의 index=0 부터 끝까지 찾고자하는 정보와 일치하는지 비교하는 알고리즘이다. 데이터의 크기가 n이라고 가정했으므로 이를 수식으로 표현하면,

\[ T(n) = n(1 + 1 + 1) = 3n \]

이라고 할 수 있다. 왜냐하면, for문이 돌 때마다 i++ 연산, i < arrayLength 연산, if문에서 array[i] == target 연산을 하기 때문에 1 + 1 + 1이라고 표현했다. 그러나, 이 시간 복잡도를 분석하는 과정에서 가장 중요한 것은 어떤 연산이 이 알고리즘의 핵심인가 를 아는 것이다. 순차탐색에서는 == 연산이 핵심이 되고 다른 연산은 ==에 의존적이다. 왜냐하면, for문이 돌다가 맞는 값을 찾으면(if 문에서 == 조건이 성립하면) < 연산과 ++ 연산을 그만두게 되기 때문이다.

그래서, 순차 탐색 알고리즘에서 시간 복잡도를 계산해보면, 최악의 경우에서

데이터 개수가 \(n\)일 때, 최악의 경우에 해당하는 연산횟수(== 연산의 횟수)는 \(n\)이다.

고로, 함수 \(T(n)\)은 다음과 같다.

\[ T(n) = n \]

Coding Future, Decoding Society.