알고리즘이란, 문제를 해결하는 절차라고 할 수 있다. 하지만, 여기서 먼저 '문제가 무엇이냐'라는 것에 대해 명확한 정의가 있어야 한다. 이 문제가 해결이 가능한 문제인가? 불가능한 문제인가? 해결이 가능하다면 어느 정도까지 답을 얻을 수 있는가에 대한 정의가 있어야 명확한 문제라고 할 수 있다. 즉, 문제는 자신에게 어떤 값이 주어지고, 어떤 결과를 얻어야 할지가 분명해야 한다는 것이다.
또, 문제를 해결하는 것에 앞서서, 누가, 어떻게 문제를 해결할 것인지도 생각해야 한다. 여기서는, 문제를 해결하는 기본 바탕으로 RAM(Random Access Machine)이라는 기계를 생각하게 된다. 이 기계는 거의 무한대의 리소스와 CPU 파워를 가지고 있다고 하자. 이제, 여기서 문제의 답을 얻는 알고리즘을 생각하였다면, 이 알고리즘의 답이 맞는 것인지, 적절한 시간과 리소스를 소모하는지, 이것보다 더 나은 알고리즘이 존재하는지 여부를 확인하는 것으로 알고리즘의 구현 절차가 마무리된다.
알고리즘의 답이 적절한지를 검증하는 절차가 중요하지만, 여기서는 논의하지 않는다. 알고리즘이 효율적인지를 다룰 뿐인데, 이것을 판단하는 방법으로는 두가지가 있다. 첫번째가 실험적인 방법(Experimental Analysis)으로, 실제 해당 알고리즘을 기계에서 구현하여 실행해서 결과를 얻는 방식이다. 하지만 이것은 쉬운 방법은 아니다. 각각의 기계마다 동일한 환경 아래서 측정이 이루어져야 하기 때문이다. 어느 알고리즘이 더 효율적인지 판단하는 입장에서는 쉬운 일이 아니다. 따라서, 실험적인 방법보다 이론적인 방법(Theoritical Analysis)으로 효율성을 측정하게 된다. 어떻게 이 방법이 가능한가? 어떤 기계에서 임의의 명령을 실행하는데 단위 시간이 소모된다고 하면, 알고리즘을 실행하는데 단위 시간에 따른 시간 소모를 예측할 수 있게 된다. 따라서, 알고리즘의 효율성을 판단하는데 각각의 알고리즘 간의 비교가 가능해진다. 알고리즘의 효율성을 측정하는데 실험적인 방법보다 이론적인 방법이 일반적이다. 여기서의 단위 시간은, Basic Operation으로 소모되는 시간을 뜻한다. Basic Operation이란, 변수 선언, 메모리에서 데이터를 가져오거나, 메모리에 데이터를 쓰는 동작 따위를 말한다.
하지만, 이론적인 방법으로 측정한 시간은 알고리즘의 정확한 수행 시간을 측정하지 못한다. 단위시간 단위로 측정되었기 때문에 실제의 시간 예측은 근사적으로 할 수 있을 뿐이며, 변수를 할당하고 값을 대입하는 시간, 그리고 알고리즘에 보이지 않는 기타 작업에 소모되는 시간이 존재하기 때문이다. 따라서, 순수하게 알고리즘의 효율성을 나타내는 방법으로 Big-O 표기를 사용하게 되는데, 이것은 알고리즘에서 가장 많은 시간을 소모하는 부분의 복잡도를 나타내는 표기법이다.
알고리즘의 효율성을 측정하는 방법으로 유용한 것은 최악의 경우를 측정하는 것과, 평균 수행시간(Average Behavior Analysis)을 측정하는 것이다. 최악의 경우를 측정하는 것은, 알고리즘이 어떤한 경우라도 그 이상의 시간을 소모하지 않는다는 것을 보장하기 때문이다. 하지만 실제로 실행 환경이 언제나 최악의 상황인 것만은 아니기 때문에, 평균 수행시간 역시 중요한 측정 요소이다.
마지막으로, 어떻게 알고리즘에 의해 얻어진 답이 맞다는 것을 검증하는가? 알고리즘에 의해 얻어진 답이 적절한지 여부는, 알고리즘이 수행되기 전의 pre-codition이 성공적으로 post-condition으로 바뀌었는지, 알고리즘이 적절하게 종료되었는지를 확인하는 것으로 검증하게 된다.
Library/Algorithm