[알고리즘] 알고리즘 분석

[알고리즘] 알고리즘 분석

 

 알고리즘을 설계한 뒤에는 알고리즘의 정확도와 효율성을 분석해야 한다. 알고리즘 분석은 크게 정확성 분석과 효율성 분석으로 나뉜다.

 

1. 정확성 분석

-정확한 알고리즘은 유효한 입력이 주어졌을 때, 유한 시간 내에 정확한 결과를 생성해야 함

-정확성 분석은 수학적 기법을 사용해 알고리즘이 예상대로 동작하는지를 증명하는 과정임

 

 

2. 효율성 분석

-효율성 분석은 알고리즘을 수행하는 데 얼마나 많은 컴퓨터 자원이 필요한지를 평가하는 과정임

-알고리즘을 수행하는 데 드는 시간적/공간적 비용을 분석하게 되며, 이를 각각 시간 복잡도/공간 복잡도라고 부른다.

 

(1) 공간 복잡도(Space complexity)

-알고리즘 수행에 필요한 총 메모리 양

-컴파일 과정에서 결정되는 정적 공간/실행 과정에서 결정되는 동적 공간으로 이루어짐.

 

(2) 시간 복잡도(Time complexity)(=알고리즘의 수행 시간)

-간단하게는 알고리즘의 실행-완수까지 걸리는 실 수행시간의 측정을 통해 계산 가능

-실행 환경에 따라 달라지기에 일반성이 없음

-알고리즘의 기본 연산 수행 횟수를 세는 방법을 통해 게산한다.

**알고리즘의 수행시간은 알고리즘에서 얼마나 많은 양의 기본 연산을 수행하는지에 따라 달라진다.

=> 알고리즘의 수행시간은 알고리즘의 각 문장이 수행되는 수의 합이다.

=> 알고리즘 수행시간은 입력 크기/입력 데이터의 상태에 따라 달라질 수 있다.

 

=> 주로 입력 크기 n의 함수로 표기한다.

=> 가장 이상적인 접근법은 가능한 모든 입력 상태에 대해 각각의 수행 시간을 계산한 뒤, 이들의 평균.가중 평균을 취하는 평균 수행시간을 사용하는 것!

=> 하지만 평균 수행시간은 특정 입력에 대한 수행시간을 나타내지 못한다. 

=> 데이터의 상태가 항상 최적이라고 가정할 수 없고, 그 외의 모든 경우에 대해서는 정보를 얻을 수 없기 때문에 일반적으로 최악 수행시간을 알고리즘의 시간 복잡도의 척도로 많이 사용한다.