Big-O 표기법

https://youtu.be/5Ky59iblLBI?list=PL3xNAKVIm80KOJ0g_OuJ7z-K9Esz4laZC

 

 

 

 

빅오 표기법이란

- 알고리즘의 성능을 나타내는 표기법

- 시간/공간 복잡도 예측 시 사용

- N 값의 증가에 따른 처리 시간 또는 필요 공간 계산

 

-> 점근적 표현법 중 하나로, 일반적으로 상수와 계수를 제거하고 복잡도를 단순화 하여 나타낸다

 

 

빅오 표기법을 사용하면 애매해질 수 있는 연산 횟수 계산법을 하나의 일관된 형식으로 만들어

알고리즘의 런타임이 인풋의 증가에 따라 어떻게 증가하는지 설명할 수 있게 해준다.

 

: 알고리즘의 직접적인 모든 연산 횟수를 계산 하는 것이 아닌, 인풋의 증가에 따른 연산 처리시간의 증가율을 예측하는 척도

 

 

 

 

빨간색이 제일 빠름

 

 

 

인풋이 증가할 수록 점점 경사가 완만해짐

 

 

 

 

 

 

 

 

 

 

 

 

 

 

빅오 표기법 규칙

- 최고차항만 표기하고, 상수항 & 영향력없는 항은 무시할 것 -> 최대한 심플화된 표현

- 상수는 인풋증가의 영향을 받지않고 일정하기 때문에 증가율 계산에 포함하지 않으며

- 영향력이 없는 항(계수항) 또한 복잡도의 증가율에 영향을 미치지않기 때문에 무시한다

 

 

 

 

 

 

 

최고차항만 신경쓰면 된다.

 

 

T(f) = (3n) * (n^2)

T(f) = 3 * n * n * n

T(f) = n^3

T(f) = O(n3)