점근표기법

점근 표기법이란?

알고리즘의 성능을 수학적으로 표기하는 방법.
알고리즘의 “효율성”을 평가.
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.

점근 표기법의 종류

• 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법

• 빅오 표기법:
  최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인가.

• 빅오메가 표기법:
  최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인가

빅오 표기법으로 표시하면 $O(N)$,
빅 오메가 표기법으로 표시하면 $Ω(1)$ 의 시간복잡도를 가진 알고리즘이다!

대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문에 알고리즘의 표기법은 빅오 표기법$O(N)$으로 한다.