시간복잡도 (빅오표기법) Time-Complexity (Big-O)

시간복잡도 Time-Complexity란?

시간복잡도는 데이터를 처리하는 과정에 있어서 얼마나 시간이 걸리는 지 확인할 수 있는 지표이다.

알고리즘의 속도를 의미한다. 

대표적으로 빅오(Big-O) 표기법을  사용한다.

 

시간복잡도 그래프

시간복잡도 비교 그래프

제일 빠른 순 부터 나열하면

Excellent/Best

1 O(1) - 일반 배열의 랜덤 Access 등에 해당함. C++ STL의 Array, Vector, List의 Random Access가 이에 해당함. 

 

Good

2 O(log n) - 이진탐색의 시간복잡도에 해당함. STL C++의 Set과 map의 컨테이너에서 find, I/O 등의 시간복잡도에 해당함.

정렬알고리즘에서는 퀵정렬의 시간복잡도에 해당함.

 

Fair

3 O(n) - For문 한 번 돌 때의 시간복잡도에 해당함. STL C++의 Vector에서 find와 I/O 부분의 시간복잡도에 해당함.

 

Bad

4 O(n log n) - 예제 없음. 그냥 이진탐색을 몇(n)번 실행하는것으로 생각하면 될 것 같다.

 

Horrible/Worst

5 O(n^2) - For문 두 번 돌 때의 시간복잡도에 해당함. 정렬 알고리즘 중에서는 삽입정렬,선택정렬, 버블정렬이 이에 해당함.

6 O(2^n) - 재귀로 표현하는 피보나치 수열. 

7 O(n!) - 예제 없음.