◎ Analysis of Algorithm
○ Empirical
analysis(경험적 분석) : 알고리즘을 프로그래밍 언어로
구현을 한 뒤, 이를 실행시켜 실시간을 비교해 보는 것
○ Mathematical analysis(수학적 분석)
: 알고리즘을 프로그래밍 언어로 구현하지 않고, 단지 알고리즘 자체만으로 수학적
분석을 하는 것
● Best case and Worst case
○ Bast case : 가장 작은 시간과 공간을 필요로 하는 경우
○ Worst case : 가장 많은 시간과 공간을 필요로 하는 경우
- 어떠한 알고리즘의 일반적인 경우 다른 알고리즘에 비해 매우 성능이 뛰어나나 최악의 경우에 많은 시간과
공간을 필요로 할 수 있는 현상이 있고, 어떤 알고리즘의 일반적인 경우는 다른 알고리즘에 비해 성능은
떨어지나 최악의 경우에도 일반적인 경우와 별 차이가 없는 현상이 있다.
- 최악의 경우는 알고리즘의 성능을 표현하는데 많이 쓰인다. 알고리즘의
속도를 표현할 때, 아무리 많은 시간과 공간이 필요한다 해도 최악의 경우를 넘지 않는다는 것을 보증할
때 쓰인다.
|
평균적 경우라는 개념도 존재하는데, 평균적인 경우를 사용하는
데에는 몇 가지의 문제점이 있다. 1. 평균적인 경우 자체가 수학적으로 매우
어려운 개념이라 확정짓기가 어렵다. 2. 평균적인 경우가 실제의 상황과 같지
않다는 점이다. |
● 알고리즘의 분석의 단계
1. 알고리즘을 판단할 수 있는 입력자료 결정
2. 알고리즘을 구성하는 동작들을 추상적이고 기본적인 동작들로 분해하여 동작들의 수행시간을 계산
3. 수학적인 알고리즘 분석
● 알고리즘의 유형
알고리즘의 분석 결과는 입력되는 자료의 수 N에 대한 수행시간을 함수 관계로 표현
★ 1
입력자료 수에 관계없이 일정한 실행시간을 갖는 알고리즘
★ log N
입력자료 수에 따라 실행시간이 조금씩 늘어남. 주로 커다란 문제를 일정한 크기를
갖는 작은 문문제 쪼갤 때 나타는 유형
★ N
입력 자료수에 따라 선형적으로 실행시간이 걸리는 경우.
★ N log N
커다란 문제를 독립적인 작은 문제로 쪼개어 각각 해결하고 나중에 다시 하나로 합치는 경우.
★ N2
이중 루프 내에서 입력자료를 처리하는 경우.
★ N3
삼중 루프 내에서 입력자료를 처리하는 경우.
★ 2N
입력자료의 수가 늘어남에 따라 급격한 실행시간의 증가.
