[알고리즘 분석]4. Running Time

목차

1. Analysis of Algorithms(알고리즘 분석)

2. Running Time

3. Experimental Studies(실험적 분석법)

4. Theoretical Analysis(이론 분석)

 

1. Analysis of Algorithms(알고리즘 분석)

<algorithms>

 Analysis of Algorithms(알고리즘 분석)은 Data Structure와 밀접한 연관이 있는 것으로, 간단히 생각하자면 function procedure(연산)이라고 할 수 있습니다.

 위의 그림과 같이, 간단히 생각하면 들어오는 Input 값을 Output 값으로 변화시키는 것을 말합니다.

 

2. Running Time

 대부분의 알고리즘은 input 값을 output 값으로 변환시킵니다. 이때, 대부분 알고리즘의 시간은 input의 size에 비례하게 됩니다.(물론 예외는 존재) 평균적으로 걸리는 시간은 계산하기 어려움으로, 가장 최악으로 걸리는 시간을 분석하는 것이 일반적입니다. 그 이유로는

- 최악의 케이스가 계산하기 쉬움

- 최악의 시간을 고려하는 것이 게임, 금융 등 관리에서 이점을 가짐

 

3. Experimental Studies(실험적 분석)

 알고리즘의 시간을 실험적으로 분석하기 위해서는 다음의 과정을 거칩니다.

1. 사용하고자 하는 알고리즘을 이용하여 직접 프로그램을 작성한다.

2. 가능한 많은 종류의 input 값을 대입하여 프로그램을 실행시킨다(input 값의 크기, 종류)

3. 프로그램 실행에 걸리는 시간을 확인하고, 모든 결과를 정리해서 비교해본다.

 

 하지만, 이런 실험적인 분석은 분명 한계점이 존재한다. 실험적 분석을 살펴보면, 몇 가지 의문점을 품을 수 있다.

1. 알고리즘을 무조건 구현해야 하며, 이 자체가 어렵다.

2. 우리가 대입한 예시 test값들이 이 프로그램의 data 모두를 대표할 수 있는지?

3. 알고리즘을 비교하려면, 같은 하드웨어와 소프트웨어여야지만 가능하다.

 

4. Theorectical Analysis(이론 분석)

 Theorectical Analysis(이론 분석)은 실제로 알고리즘을 구현하는 대신에, 알고리즘에 대한 high-level description(높은 수준의 생각)을 사용합니다. 앞으로 input의 크기는 통틀어서 n이라고 할 것이며, 이것이 통상적인 방법입니다.

 결국 이론 분석은, 소요되는 시간 혹은 할당되는 메모리의 크기 등을 크기 n에 대한 함수로 나타내는 것을 말합니다. 최악의 경우, 혹은 평균의 크기 n의 함수를 가상의 컴퓨터에서 실행했을 경우를 고려하여 계산하는 것입니다.