Asymptotic analysis, 점근적 표기법.

알고리즘의 성능을 분석하기위해 점근적 표기법을 이용해 시간복잡도 사용한다.
단순히 특정 입력 값에 따른 실행시간(running time)을 비교하는게 아니라, 입력값이 증가함에 따른 Running time의 rate of growth를 표현한 것이 시간 복잡도(time complexity)이다.
​

​Big-theta

Running time에 대한 점근적인 한계값을 Big theta라 한다.
즉, 알고리즘의 평균 시간복잡도를 말한다.


​Big-O

빅오는 running time에 대한 점근적인 상한값을 말한다.
즉, 알고리즘의 최악의 시간 복잡도이다.
보편적으로 ‘시간 복잡도’는 최악의 케이스를 커버하능 빅오를 말한다.


​Big-omega

빅 오메가는 running time에 대한 점근적인 하한값을 말한다.
즉, 알고리즘의 최선의 시간 복잡도이다.
대체로 성능을 측정할 때 최선의 경우를 고려하지는 않기 때문에, 빅 오메가는 거의 사용되지 않는다.