시간복잡도, 빅 오 표기법

 

시간복잡도

시간복잡도란 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산적인 복잡도를 의미합니다.

컴퓨터 공학에서 시간복잡도를 나타낼 때 빅 오 표기법을 사용하는데, 입력값 N이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법입니다.

 

 

빅오 표기법의 종류

1. O(1): 입력값의 크기와 상관없이 일정한 실행시간을 보장. 최고의 알고리즘이라 할 수 있다. 

2. O(log n) : 로그 함수를 생각해보자. n이 무한히 커져도 값의 차이는 매우 작다고 볼 수 있다. 아주 효율적인 알고리즘. 이진 탐색(Binary-Search)의 경우가 이에 해당한다.

이진탐색 알고리즘은 정렬된 배열 또는 리스트에서 고속으로 탐색할 때 사용된다.

3. O(n): 알고리즘을 수행하는데 걸리는 시간이 입력값에 비례하는 선형 시간 알고리즘이다.

모든 입력값을 적어도 한 번 이상은 살펴봐야 하는 경우이다. 정렬되지 않은 배열, 리스트에서 최소 최대값을 찾는 경우이다.

4. O (n log n) : 대부분 효율이 좋은 알고리즘이다. 그 예로는 병합정렬(merge sort)이 있다.

5. O(n^2) :  비효율적인 정렬 알고리즘으로, 예로 버블 정렬이 있다.

6. O(2^n) : 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 한다. n^2와 혼동되는 경우가 있는데 2^n이 훨씬 더 크다.

7. O(n!) : 가장 느린, 최악의 알고리즘. 값이 조금만 커져도 계산하기 힘들다.

 

 

입력값이 1000~2000개 정도라면 수행 효율면에서 차이를 느끼기 힘들지만, N 이 10만, 100만, ..... 점점 커질수록 수행 시간에 엄청난 차이가 벌어질 수 있습니다. 

따라서 알고리즘은 시간 복잡도를 고려하여 설계해야 합니다.