[알고리즘] 시간복잡도 (Time Complexity)

[알고리즘] 시간복잡도 (Time Complexity)

• 시간 복잡도란?

- Input 에서 Output이 될 때 까지 걸리는 시간

- 알고리즘을 구성한 명령어가 실행된 횟수 (frequency of calling command)

- 알고리즘 배울 때의 핵심은 공간, 시간 을 이용하는 것. 이 때, 공간과 시간은 거의 항상 반비례하다.

- 즉, 어떤 알고리즘이 얼마나 걸리느냐? 이다. (CPU 사용량)

[ cf ] 공간 복잡도 = 메모리를 얼마나 사용하는지에 대한 용량 개념

  어떤 알고리즘이 메모리를 얼마나 쓰느냐? (RAM 사용량)

  공간이냐? 시간이냐? 면 요즘은 시간이 우선이다.

• 시간 복잡도를 고려하는 것은 최적화를 위해 필요하다.

(다만, 데이터를 저장할 수 있는 메모리와 저장매체의 발전 덕에 과거보다는 덜 필요하다)

• 시간 복잡도 그래프(Big-O Complexity)

• 시간 복잡도가 빠른 순

O(logn) > O(n) > O(nlogn) > O(n^2) > O(n^3) > O(2^n) > O(n!)

• 시간들의 설명

- O(1) : 입력자료의 수에 관계없이 일정한 실행시간을 갖음

- O(logn) : 입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가 

 EX > 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타남

 EX > 이진탐색 같은 효율이 좋은 검색 알고리즘

- O(n) : 입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우  - 입력자료마다 일정 시간 할당

- O(nlogn) : 큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우

  EX > 효율 좋은 정렬 알고리즘

  EX > quick sorting / heap sorting 등

- O(n^2) : 이중 루프내에서 입력 자료를 처리할 때

  EX > 인접행렬이용한 bfs/dfs 알고리즘

- O(n^3) : 삼중 루프 내에서 입력자료 처리할 때

• 시간복잡도의 계산

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

ex)

void  Func(int *a, n)

{

     int i=0, j=0;                                       1

     for (i = 0 ; i < n-1 ; i++)                      n                 [i => 0 to n-1 ∴ n times called]

         for(j=i+1; j<n ; j++)                        (n-1) * n       [j => 1 to n    ∴ n times called]

            if (a[i] == a[j]) a[j] = 0 ;            (n-1) * (n-1)  [if 문은 결국 n-1 번만 실행 ]

}

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

출처: http://cafielo.tistory.com/entry/시간복잡도-개념-및-구하기 [cafielo]