시간의 복잡도 총정리(알고리즘)

시간 복잡도(알고리즘)
 

0. 들어가기 앞서서
 
자료구조와 알고리즘을 배울때 핵심은 공간과 시간 이용이다.
공간과 시간은 거의 항상 반비례하는 경향이있다.

시간복잡도: 어떤 알고리즘이 얼마나 걸리느냐(CPU사용량)
공간복잡도: 어떤 알고리즘이 메모리를 얼마나 쓰느냐(RAM사용량)

1.시간의 복잡도에 나타나는 수들 (맨날 까먹으니 웬만하면 외우자)

1(constant): 입력자료의 수에 관계 없이 일정한 실행 시간을 갖는 알고리즘

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

N(Linear): 입력 자료의 수에 따라 선형적으로 실행 시간이 걸리는 경우이다. 이는 입력 자료 각각에 일정 정도의 동일한 처리를 할때 나타나는 경우이다.

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

N²(quadratic): 이 유형은 이중루프내에서 입력 자료를 처리 하는 경우에 나타난다. N값이 큰값이 되면 실행 시간은 감당하지 못할 정도로 커지게 된다.

N³(Cubic): 이 유형은 앞의 유형과 비슷하게 입력 자료를 삼중 루프내에서 처리하는 경우에 나타난다.

2ⁿ : 입력자료의 수가 늘어남에 따라 급격히 실행 시간이 늘어난다. 이 유형은 흔하지는 않지만 가끔씩 알고리즘을 처음 개발할 떄 보인다.

 

2. 시간의 복잡도란?
 

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

                      +

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

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

시간의 복잡도는 크게 세가지로 나눌 수 있다.

최상의 경우, 최악의 경우, 평균 => 이래서 표기법도 3개가 존재하는것이다.

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

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

3.시간 복잡도 표현법
 

Big O Noration(빅-오 표기법) --- O(N)

가장 많이 쓰이는 표기법으로 알고리즘 실행시간의 상한을 나타낸 표기법(최악의 경우)

Ω(오메가)표기법 --  Ω(N)

오메가 표기법은 알고리즘 실행시간의 하한을 나타낸 표기법 (최상의 경우)

Θ(세타)표기법 --- Θ(N)

세타 표기법은 알고리즘 실행시간의 평균시간을 나타낸 표기법(평균의 경우)

4.시간의 복잡도 계산법
 

명령이 끝날때마다 실행 횟수를 적어봅니다.

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

}

시간복잡도 O(size)
총 실행횟수 : 2size +4  => O(N) 

[출처] 시간복잡도 계산|작성자 gamjamat