시간 복잡도(Time complexity) 연산에 따른 빅오표기법

연산 크기 순서
O(1) < O(log n)  < O(n)  < O(n log n) < O(n2)  < O(n3)  < O(2n)  < O(n!) < O(∞)

* 시간 복잡도 연산 크기가 작은 순서대로 작성, 번호가 올라갈 수록 연산의 크기가 증가 * 

시간 복잡도란? = 얼마나 빠른가

 

1. O(c) 또는 O(1) : 상수 시간 알고리즘 

- 입력 갯수에 관계 없이 수행 속도(계산 횟수)는 1번 = 가장 효율적임

- 백준 24262번이 상수 시간 알고리즘

https://www.acmicpc.net/problem/24262

 

2. O(log n) : 로그 시간 알고리즘

- 데이터가 2배로 증가할 때, 연산의 수가 1단계 늘어나는 형태 ex. 이진검색

 

3. O(n) : 선형 시간 알고리즘

- 입력 개수에 비례적으로 수행 시간이 길어지며, 최악의 경우에는 입력 개수만큼 연산을 수행함 ex. 선형 검색, 중첩이 아닌 일반 반복문

 

4. O(n log n) : n 로그 시간 알고리즘

- ex. 반복문 증가 스텝이 2의 배수로 하여 2,4,8,16,32,64처럼 증가하는 경우 등

 

5. O(n2) : 평방 시간(2차 시간) 알고리즘

- ex. 2번 중첩된 반복문 = n이 적을 경우에만 사용해야함

 

6. O(n3) : 3차 시간 알고리즘

- ex. 중첩된 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘들

 

7. O(2n) 또는 O(rn) : 지수 시간(exponential time) 알고리즘

- ex. n이 하나 증가할 때마다 걸리는 시간이 그 전보다 2배 또는 r배로 증가하는 나쁜 사례

 

8. O(n!) : 계승 시간(factorial time)  알고리즘

- ex. 지수 시간보다 더 많이 걸림 (더 빠르게 증가) 따라서, 초 지수 시간(super-exponential)이라고도 함

 

9. O(∞) : 종료되지 않는 무한 루프

 

[출처] http://www.ktword.co.kr/test/view/view.php?m_temp1=6146