[알고리즘 과제] 알고리즘 분석 방법

1. 알고리즘의 우수함을 가리는 기준

1) 정확성

- 정확하게 동작하는가?

- 입력값에 대한 정확한 출력을 몇 번 제공하는지를 나타냄

 

2) 작업량

- 얼마나 적은 연산을 수행하는가?

- 프로그램의 코드 길이가 가능할 짧을 것

- 예: 버블 정렬의 비교 연산 횟수, 이진 탐색의 거치는 노드의 개수

 

3) 메모리 사용량

- 얼마나 적은 주기억장치(RAM)를 사용하는가?

- 요즘에는 주기억장치(RAM) 용량이 매우 크지만, 여전히 중요한 기준임

 

4) 단순성

- 알고리즘이 얼마나 단순한가?

- 단순성을 만족하는 알고리즘의 예로는 이진 탐색, 퀵 정렬 등이 있음

 

5) 최적성

- 개선의 여지가 없을 만큼 최적화되어 있는가?

- 최적의 성능을 위하여 개선 가능한 모든 요소(작업량, 메모리, 사용량) 최적화

- 알고리즘의 성능 측정 필요

 

2. 알고리즘의 수행 시간 분석

알고리즘 수행 시간은 컴퓨터의 성능과 관계없이 명확하게 정의될 수 있어야 한다.

 

① 최악의 경우(worst case): Big O 또는 Order-of-N : O(n)

② 평균의 경우(average case): Big Theta : Θ(n)

③ 최상의 경우(best case): Big Omega : Ω(n)

 

3. 점근 표기법

점근 표기법(asymptotic)은 알고리즘의 수행 시간을 대략적으로 나타내는 방법이다. 일반적으로 가장 많이 사용하는 Big O 표기법을 기준으로, 최고차항으로만 알고리즘의 성능을 대략적으로 표시한다. 알고리즘의 성능을 단순화해서 표현하기 때문에 여러 알고리즘 간의 성능 비교에 용이하다. 점근 표기법으로 나타내기 위해서는 다음 과정을 거친다.

 

① 최고차항을 제외한 나머지 모든 항을 제거한다.

② 모든 계수를 제거한다.

 

점근 표기법을 적용한 예는 다음과 같다.

 

아래의 표는 Big O 표기법으로 표현한 대표적인 알고리즘의 성능이다.