알고리즘 - 복잡도 | protect-me

복잡도 종류

시간 복잡도 : 실행 속도
공간 복잡도 : 메모리 크기

알고리즘은 주로 시간 복잡도로 판단하며,
알고리즘의 시간 복잡도는 반복문으로 판단함.

복잡도 구분

Ω(오메가) : 최상 실행 시간
θ(세타) : 평균 실행 시간
Big O(빅 오) : 최악 실행 시간
but, 주로 수행 시간의 상한을 의미하는 Big O를 사용

Big-O 표기법

최고차항만을 표기, 상수항은 무시
ex) 3$x^2$ + 4$x$ + 5 => $x^2$

O(1) < O($logn$) < O($n$) < O($nlogn$) < O($n^2$) < O($2^n$) < O($n!$)
(뒤로 갈수록 시간이 오래 걸림)

이미지 출처