◼︎ 3-2 대문자 O 표기법

A 65536 → O(1)

65536은 n 값의 변화와 관계가 없습니다.

 

B n-1 → O(n)

n이 굉장히 커지면 -1은 거의 영향이 없어집니다.

 

C

n이 굉장히 커지면 과 비교했을 때 10000n의 영향은 작아집니다. 제곱에 비례한다는 관계가 핵심이므로 계수 도 생략됩니다.

 

D 3n⁴-4n³+5n²-6n+7 → O(n⁴)

n의 변화에 따라 가장 크게 변하는 항을 계수를 생략하여 표현합니다.

 

대문자 O 표기법의 정확한 수학적 정의에 따르면, 한 식에 대한 대문자 O 표기법은 딱 하나만 정답이 아닙니다. 하지만 O 뒤에 붙은 소괄호 안에 담긴 값을 최대한 간단히 적는 것이 가장 일반적인 방식입니다. 대문자 O 표기법의 정의가 궁금하다면 다음 링크를 참고하기 바랍니다.

• https://ko.wikipedia.org/wiki/점근_표기법