빅 오 표기법이란(Big O) - 알고리즘과 시간복잡도로 보는 빅 오 표기법

빅 오 표기법 ( Big O )

알고리즘의 효율성을 표기하는 표기법

데이터(n)개가 주어졌을 때 + - * / 같은 기본 연산의 횟수 의미

 

빅오 표기법 주 사용처
시간복잡도	공간복잡도
알고리즘의 시간 효율성 알고리즘이 수행된느 시간	알고리즘의 메모리 효율성  알고리즘을 수행하기 위해 사용되는 메모리 양

 

ex) 내가 5,000원을 가지고 있을때 표현 방식
빅오(Big-O)	빅오메가(big-Ω)	빅세타(big-Θ)
"나는 10,000원 보다 적게 있어"	"나는 10원 이상은 있어"	"한 3,000원에서 7,000원 사이?"

 

 

시간복잡도로 보는 Big O 빅오 표기법

T(n) 시간복잡도 함수

연산 횟수가 얼마나 변하는 지 그 정도를 판단

 

 

데이터의 개수 : n

즉 최고항의 차수 = Big O 임

 

 

시간복잡도의 성능 비교

알고리즘에서의 빅오 표기법 예제

 

 

출처 https://noahlogs.tistory.com/27

 

 

Big O

목표 : 장기적으로 데이터가 증가함에 따라 알고리즘의 효율성을 측정 

상수 과감하게 삭제