알고리즘 개념 2. 점근적 표기 (Asymptotic notation)

점근적 분석?

- 주어진 문제에 대한 여러 알고리즘이 있을때, 효율성을 비교하기위한 분석

 

점근적 증가율?

- 변수크기가 충분히 크면 변수증가에 따라 함수가 증가하는 비율(함수를 비교할 때, 상수나 작은 인풋은 무시)

 

 

점근적 표기법?

 

(1) O-표기법

- 알고리즘이 아무리 안좋아도, 비교하는 함수와 같거나, 그거보다 좋다

- 점근적 상한선(Asymptotic upper bound)만 알고있다면 이 표기법 사용

- (ex)이 알고리즘은 적어도 00정도의 성능이 나온다 할때 사용

- 

 

(2) 𝛺-표기법

- 알고리즘이 아무리 좋아도, 기존 비교하는 함수 이하이다.

- 점근적 하한선(Asymptotic lower bound)

- O-표기법의 반대개념

-

 

(3) 𝛩-표기법

- 알고리즘이 아무리 좋아도,나빠도, 기존 함수의 성능 범위안에 있다.

- 점근적 상한과 하한의 교집합(Asymptotic tighter bound)

 

 

수식적표현은 곧 다시 공부하기