[알고리즘] 점근성능

[알고리즘] 점근성능

 

1. 점근성능(Asymptotic Performance)

-입력 크기에 따라 알고리즘의 성능도 변하기 때문에, 입력 크기 n이 충분히 큰 상태를 전제로 성능을 분석하는 것이 바람직하다.

-입력크기 n이 무한히 커짐에 따라 결정되는 성능을 점근 성능이라고 부른다.

-알고리즘 간의 우열을 평가할 때는 입력 크기 n의 차수만을 표기한다.

-수행시간은 최고 차수를 가진 항에 의해 가장 큰 영향을 받아 결정된다. 따라서 최고차항만을 계수 없이 단순화한 형태로 성능을 표현한다.

 

-> 알고리즘간의 우열을 따질 때 유용하다.

-> 점근성능 표기법으로는 O(Big-Oh 빅-오)표기가 대표적이다.

 

 

2. 점근성능 표기법

-점근성능을 표기하는 방법으로는 주로 O(Big-Oh), Ω(Big-Omega), Θ(Big-Theta) 총 세 가지가 있다.

1. O(Big-Oh/점근적 상한): 최악의 수행시간.
2.  Ω(Big-Omega/점근적 하한): 최선의 수행시간
3. Θ(Big-Theta/점근적 상하한): 점근적 상한과 하한을 동시에 가지는 값. 다른 표기법보다 정확하게 성능을 나타낼 수 있다.

*알고리즘의 시간 복잡도-크기 관계

*여기서 O(1)은 입력 크기에 관계없이 수행시간이 언제나 일정하다는 것을 의미한다.

작은 순<->큰 순
O(1)	O(log n)	O(n)	O(n log n)	O(n의 제곱)	O(n의 세제곱)	O(2의 n제곱)