Big-O 표기법

빅오 표기법(Big-O notation) 이란 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법입니다.

 

 

예를들어서 10n² + n 이 있을때, 시간복잡도에 가장 영향을 많이 미치는 것은 n² 입니다.

 

왜냐하면 1부터 대입해보면

n² : 1, 4, 9, 16, 25 ,36 … 

n :  1 ,2 3, 4, 5, 6, 

n보다 n²의 증가가 더 급격한 걸 볼 수 있습니다.

그래서 영향력이 적은 항 제거, 상수항 제거하여

10n² + n는 다음과 같이 표기할 수 있습니다.

O(n²)