알고리즘의 성능 분석 방법

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

성능 분석 방법이 필요한 이유는 우리가 자료를 처리할 때 단순이 잘 돌아만 가는 것을 원하는게 아니라 어떠한 상황에서도 우월한 성능을 내기를 원하기 때문이다.

▶알고리즘을 평가하는 두 가지 요소

시간 복잡도(Time Complexity) : 얼마나 빠른가

공간 복잡도(Space complexity) : 얼마나 메모리를 적게 사용하는가

사실 메모리를 적게 쓰고 속도도 빠른 알고리즘이 최적의 알고리즘이다. 하지만 대개 알고지즘을 평가할 때는 메모리 사용량보다 속도에 초점을 둔다.

▶성능을 평가하는 방법

성능은 어떻게 평가할까?

위의 표를 보면 2개의 알고리즘 A,B가 있다. 이 두개의 A,B를 비교해 보자

위의 표만 보면 기준을 두 가지로 나눌 수 있다. 즉 데이터가 n보다 작을때와 클 때의 두 가지로 나눌 수 있을 것이다. 자, 그럼 어떤 알고리즘이 더 좋은 알고리즘일까?

정답은 A 알고리즘이다.

이유는 데이터의 수가 적은 둘 간의 속도 차이가 얼마나 나겠는가? 중요한 것은 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도에 있다.

하지만 A 알고리즘이 더 좋다고 해서 B 알고리즘이 없어도 된다는 말은 하면 안 된다. 

A알고리즘의 경우 B 알고리즘보다 구현이 더 어렵기 때문에 데이터가 적은 경우에는 B를 선택해도 되기 때문이다.

결국, 하고 싶은 말은 상황에 맞게 답을 내려 쓰자는 것이다. (여기서 A가 맞는 이유는 자료구조는 적은 데이터에서 보다 많은 데이터에서 최상의 효율을 내는 알고리즘을 필요로 하기 때문) 

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

'순차 탐색 알고리즘'으로 시간 복잡도를 계산해 보고자 한다.

#include<stdio.h>
 
int LSearch(int ar[], int len, int target) {
    for (int i = 0; i < len; i ++ ) {
        if (ar[i] == target)
            return i;    //찾은 대상의 인덱스 값 반환
    }
    return -1;    //찾지 못했음을 의미하는 값 반환
}
 
int main() {
    int arr[] = { 3,5,2,4,9 };
    int idx;
 
    idx = LSearch(arr, sizeof(arr) / sizeof(int), 4);
    if (idx == -1)
        print("탐색 실패\n");
    else
        print("타켓 저장 인덱스 :%d\n", idx);
    return 0;
}

실행 결과는 

타켓 저장 인덱스 : 3

위 예제는 C언어를 공부하면서 한 번 정도는 구현해 봤을법한 순차 탐색 알고리즘이다. 이제 이 알고리즘을 실제로 구현하는 코드만 봐 보자.

for (int i = 0; i < len; i ++ ) {
    if (ar[i] == target)
        return i;    
}

이제 위의 코드를 토대로 시간 복잡도를 분석해 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구해보자.

위 알고리즘에서 연산자는 <, ++, == 총 3개이이다. 여기서 가장 핵심 연산자는 뭘까?

바로 == 연산자이다.  == 연산자를 적게 사용하면 < 연산자와 ++ 연산자를 적게 사용하고, ==연산자를 많이 사용하면 < 연산자와 ++ 연산자를 많이 사용하게 된다. 

이렇듯 알고리즘의 핵심 연산이 무엇인지 잘 판단해야 한다. 그리고 그 연산자 중심으로 시간 복잡도를 계산해야 한다.

최선의 경우, 최악의 경우, 평균적인 경우

대부분의 경우에는 알고리즘의 분석을 최악의 경우를 분석한다. 최악의 경우를 분석하는 것은, 수행 시간의 upper bound(상한)을 알 수 있게 해주고 이것은 알괴즘에 대한 좋은 정보가 될 수 있다. 

평균적인 경우를 분석한느 것은 몇몇 경우를 분석하는 만큼 쉬운 것은 아니고, 수학적인 모든 경우의 수를 알아야 한다.

최선의 경우를 분석하는 것도 알고리즘의 lower bound(하한)을 구하는 것은 최악의 겨우에 대한 어떠한 정보도 제공해주지 않기 때문에 알고리즘은 몇년간 수행될 수도 있다.

최악의 경우의 시간 복잡도 계산

순차 탐색 알고리즘을 보면 데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는(비교연산의 횟수는)n 이라는 것을 알 수 있다.

따라서 순차 탐색 알고리즘의 '데이터 수 n에 대한 연산횟수의 함수 T(n)'은 다음과 같다.

우리가 이 파트에서 다룰 내용은 알고리즘의 성는 분석이였다. 

"와우, 그럼 알고리즘의 성능은 T(n)으로 표연하는구나" 하고 넘어갈 수 있다.

하지만 그래서는 안된다.

좀 김 빠질 수 있지만 이제 진짜 성능을 나타내는 방법을 이야기할 것이다.

빅 - 오 표기법(Big oh Notation)

빅오는 대부분 최악의 경우를 표현한다.

위의 과정을 보면 가장 최고차항이 높은 식을 가리켜 빅오의 값으로 얻고 있다. 왜 나머지는 버리는 것일까?

다음 표를 보면서 이해해보자

표에서 보이듯이 데이터의 수(n)이 증가할수록 최고차항이 차지하는 비율은 절대적이다. 따라서 성능을 평가 할 때에는 항상 가장 높은 차항의 값을 데이터화 하여 개선 방안을 찾아 내어야 한다.

빅 - 오 표기법의 종류와 성능

빅-오 표기법의 종류

● O(1) - (상수) Constant

- 입력되는 데이터의 양과 상관없이 일정한 실행 시간을 가지낟.

- 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.

● O(logN) Logarithmic

- 데이터의 양이 많아져도, 연산횟수가 조금씩 늘어난다.

- 시간에 비례하여, 탐색 가능한 데이터의 양이 2의 n승이 된다.

- 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

- 만약 입력 자료의 수에 따라 실행 시간이 이 logN의 관계를 만족한다면 N이 증    가함에 따라 연산횟수가 조금씩 늘어난다. 이 유형은 주로 커다란 문제를 일정    한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형이다.

- Binary Search(이진 탐색 알고리즘)

● O(N) Linear

- 데이터의 야에 따라 시간이 정비례한다.

- 순차 탐색 알고리즘(Linear search), for 문을 통한 탐색을 생각하면 된다.

● O(N logN) log linear

- 데이터의 양이 N배 많아 진다면, 실행 시간은 N배 보다 조금 더 많아 진다.(정비례 안함)

- 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대한 독립적으      로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타난다. N이 두배    로 늘어나면 연산횟우는 2배도다 약간 더 많이 늘어난다.

- 퀵소트, 머지소트

● O(N^2) Puadratic

- 데이터의 양에 따라 걸리는 시간은 제곱에  비례한다.(효율 쓰레기, 사용 절대      안 됨)

- 이 유형은 이중 루프 내에서 입력 자료를 처리하는 경우에 나타난다. N값이 큰 

  값이 되면 연산 횟수를 감당할 수 없게 된다.

- 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱

- 2중 for문을 사용하는 버블 소트, 삽입정렬(insertion sort)

성능비교

성능 순서 :  O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)

--------------------------------------------------------------------

위 글은 <윤성우의 열혈 자료구조>를 보고 정리한 글입니다.