시간복잡도

알고리즘을 수행하는 데 평균적으로, 또는 최악의 경우 얼마만큼의 시간이 걸리는 지 보여주는 지표
공간의 복잡도도 있다. 알고리즘이 얼마만큼의 메모리를 차지하는 지 보여주는 것.

빅오 표기법

주로 이용하는 표기법
최악의 경우 걸리는 시간이다. 모든 경우에 이 시간이 걸린다는 것은 아니다.

빅오 순서는

O(1) O(logN) O(N) O(NlogN) O(N^2) O(N^3) ... O(2^N) O(N!)

로그는 항상 밑이 2인 로그를 기준으로 한다.

• 최상의 경우: 오메가 표기법
• 평균의 경우 : 세타 표기법
• 최악의 경우 : 빅오 표기법

https://kjwsx23.tistory.com/339- logN 과 NlogN이 도출되는 과정(병합정렬과 이분탐색)