시간복잡도

하나의 알고리즘이 문제를 해결하는 데 소요되는 시간

빅오(Big-O) : 최악
빅오메가(Big-Ω) : 최선
빅세타(Big-Θ) : 평균
세가지 표기 방법이 있다.

최악의 경우를 고려하는 Big-O 표기법을 주로 사용한다.

Big-O 시간복잡도

최고 차항을 제외한 모든 항과 최고차항의 계수를 제외시킨다

1. $O(1)$

상수

2. $O(logn)$

로그
이진 탐색

3. $O(n)$

선형

4. $O(nlogn)$

선형 로그
퀵정렬, 병합정렬, 힙정렬

5. $O(n^2)$

다차

6. $O(2^n)$

지수

7. $O(n!)$

팩토리얼

정렬 알고리즘의 시간복잡도

알고리즘	최선	평균	최악
선택 정렬	n^2	n^2	n^2
삽입 정렬	n	n^2	n^2
버블 정렬	n	n^2	n^2
힙 정렬	nlogn	nlogn	nlogn
퀵 정렬	nlogn	nlogn	n^2
병합 정렬	nlogn	nlogn	nlogn