알고리즘의 분석 : 시간 복잡도 & 공간 복잡도

알고리즘의 효율성을 평가하는데 있어서
그 기준은 크게 2가지로 잡는다고 한다.

하나는 시간. 그리고 공간이 바로 그것이다.

간단하게 설명하면
시간 복잡도는 얼마나 빠르게 실행되느냐에 대한 것이고
공간 복잡도는 얼마나 메모리를 많이 차지하느냐에 대한 것이다.

가장 좋은 알고리즘은 시간은 적게 걸리고 메모리의 사용은 적어야 하는거겠지.

시간과 공간은 반비례 하는 경향이 있다.

요즘은 공간보다는 시간이 우선이다!

일반적으로 알고리즘의 분석(analysis of algorithm)이라 함은

알고리즘을 이루는 명령어들의 수행횟수를 계산하여 알고리즘의 시간 복잡도를 구하는 일을 일컫는다.


여기서 시간의 복잡도란

알고리즘을 구성하는 명령어들이 몇번이나 실행됬는지 센 결과(frequency count)

                      +

각 명령어의 실행시간(execution time) 을 곱한 합계를 의미함!!!

 

그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다.

 

먼저 시간 복잡도의 점근적 표현법부터 알아보자

점근적이라는 것은 정확하다는 것과 비교해보면 이해하기 쉽다.

정확한 계산은 실제 실행 횟수를 계산한다.

즉, 정확한 계산은 헤아려야 할 부분이 너무 많다.

점근적 계산은 가장 큰 영향을 주는 항만 계산한다.

즉, 가장 중요한 항만 고려하므로 간단하다.

시간 복잡도의 3가지 점근적 표현법

O()-빅오

Ω()-오메가

Θ()-세타

라고 3 종류가 있다. 

쉽게 이해하려면

O()는 최악의 경우
Ω()는 최상의 경우

Θ()는 평균의 경우

라고 볼 수 있겠다. 

시간의 복잡도 계산법은 명령이 끝날때마다 실행 횟수를 적어본다.

ex)

void  Func(int *a, n)

{

     int i=0, j=0;                                       1

     for (i = 0 ; i < n-1 ; i++)                      n      (i =0일때부터 i=n-1일때까지 계속 실행됨)

         for(j=i+1; j<n ; j++)                        (n-1) * n (가장 많이 수행되는 경우를 생각)

            if (a[i] == a[j]) a[j] = 0 ;            (n-1) * (n-1)

}

 

명령어 실행횟수를 모두 더하면 2n²-2n+2  ->상수는 생략하고 최고차항만 생각한다. => O(n²)로 표기한다.

 

ex)

int Func2(int a[], int size, int key)  {

   int i = 0;                                          1

   for (i = 0; i < size; i++)                      size + 1

       if(a[i] == key)                              size

       return i;                                      1

   return -1;                                        1

}

총 실행횟수 : 2size +4  => O(N)  

만약,

두 알고리즘 A, B가 아래와 같을 때,

A 알고리즘 : T(n) = 3n² + 2n + 5

B 알고리즘 : T(n) = n³ + 3n² +1

알고리즘 A, B의 시간복잡도(Time Complexity)를

빅오(Big O) 표기법으로 표시하면 아래와 같다.

A 알고리즘 : Ot(n) = n²

B 알고리즘 : Ot(n) = n³

빅오 표기법으로 표시된 위의 두 알고리즘의 시간복잡도를 비교한다.

만약, 입력(n)이 n=100 이라고 하면,

A 알고리즘은 O(n) = n² 이므로 10,000 번의 비교연산을 수행하게 된다.

B 알고리즘은 O(n) = n³ 이므로 1,000,000 번의 비교연산을 수행하게 된다.

따라서, 알고리즘B는 입력의 갯수가 커지면 커질수록 알고리즘A에 비하여 기하급수적인

시간비용을 초래한다. 그러므로, 처리속도면에서 알고리즘 A가 우수하다는 것을 알 수 있다.


마지막으로 시간복잡도 빅오의 순서는 다음과 같다.
커질수록 느려짐.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)