빅오 표기법(big-O notation)

 빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다. 

알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.

빅오 표기법의 특징

 

1. 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.

예를들어

 와 같이 상수항은 무시하고 표기한다.

2. 영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

예를들어

와 같이 영향력이 지배적인 

이외에 영향력이 없는 항들은 무시한다.

 

 

출처 : 이것이 취업을 위한 코딩 테스트다 - 지음:나동빈

출처: https://noahlogs.tistory.com/27 [인생의 로그캣]