_04.[관련용어]빅오 표기법

빅오 표기법의 종류

1. O(1)

 입력값이 아무리 커도 실행 시간은 일정합니다.

 O(1)에 시행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당합니다.

 

2. O(logn)

 실행 시간이 입력값에 영향을 받습니다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고합니다.

 대표적으로 이진 검색이 이에 해당합니다.

 

3. O(n)

 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값이 비례합니다.

 이러한 알고리즘을 선형 시간 알고리즘이라고 합니다.

 정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 합니다.

 

4. O(n logn)

 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당합니다.

 입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트(Timsort)가 이런 로직을 갖고 있습니다.

 

5. O(n2n2)

 버블 정렬 같은 비효율적 정렬 알고리즘이 이에 해당합니다.

 

6. O(2n2n)

 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당합니다.

 n2n2보다 2n2n이 훨씬 큽니다.

 

7. O(n!)

 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당합니다.

 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵습니다.

 

 

자료출처: deep-learning-study.tistory.com/434?category=978143