[알고리즘] 1_2 알고리즘 기본

1.13 분석의 종류

 - 주어진 알고리즘을 분석하기 위해서는 어떤 입력에 대해 더 적은 시간이 걸리고( 잘 수행되고 ), 어떤 입력에서 더 오랜 시간이 걸리는지 알아야 한다.

 -알고리즘을  수식으로 표현하여 점근적(asymptotic) 분석/표기법의 기초를 이루는 일종의 문법이 필요하다. 세 가지 종류의 분석이 있다.

 - 최악의 경우

   - 알고리즘이 오래 걸리는 경우이다.

   - 알고리즘이 느리게 수행되도록 하는 것을 입력으로 한다.

 - 최선의 경우

   - 알고리즘이 제일 적은 시간이 걸리게 하는 경우이다.

   - 알고리즘이 가장 빨리 수행되도록 하는 것을 입력으로 한다.

 - 평균의 경우

   - 알고리즘의 예상 수행 시간을 제시한다.

   - 입력이 무작위라고 가정한다.

   하한 시간 ≤  평균 시간 ≤ 상한 시간

 - 주어진 알고리즘에 대해 최선, 최악, 평균의 경우를 수식으로 표현할 수 있다.

1.14 점근적 표기법

1.15 빅-오 표기법

1.16 오메가 표기법

1.17 세타 표기법