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

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

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)