본문 바로가기

Library/Algorithm

알고리즘의 최적성 분석 문제의 복잡도를 알고, 문제를 해결할 알고리즘의 최악의 경우를 알고 있다고 하자. 해결 알고리즘의 최악의 경우를 W(n)이라 하고, 문제의 복잡도를 F(n)이라 했을 때, W(n) != F(n)이라면 2가지 결론을 얻을 수 있다. 첫째, 이 해결 알고리즘이 문제를 해결하는 최적의 알고리즘이 아닐 수도 있다는 것, 둘째, 그것이 아니라면 문제의 하한(lower bound)이 너무 낮게 잡혀있다는 것이다. 같지 않다고 해서 항상 해결 알고리즘이 최적의 알고리즘을 구현하지 못한 것은 아니다. 문제의 복잡도를 나타내는 하한(lower bound)는 더 높아질수록 현실적인 값이 된다. 반대로, 알고리즘은 상한(upper bound)에서 더 낮아질수록 더 좋은 알고리즘이 된다. 정렬된 입력값에 대해서, 어떤 값을 .. 더보기
알고리즘의 분석과 문제의 분석 알고리즘을 분석한다는 것은, 얻은 결과가 맞는 것인지, 어느 정도의 시간을 소모하는지, 어느 정도 최적화가 되어 있는지의 3가지 여부를 확인하는 것으로 이루어진다. 어느 정도의 시간을 소모하는지는 Big-O 표기를 사용하며, 주로 최악의 경우와 평균 수행 시간을 분석하는 것으로 이루어진다. 시간 복잡도 외에도, 메모리와 같은 리소스의 사용량도 Big-O 표기를 이용하여 나타낼 수 있다. 최적화에 대한 분석은 어떻게 이루어지는가? 먼저, 어떤 문제를 해결하기 위해서, 주어진 문제가 필요한 최소한의 연산의 필요한지 파악할 필요가 있다. 즉, Big-O 표기가 '이것보다 더 복잡하거나 시간을 소모하지 않는다'라는 의미라면, 문제의 최적의 답을 얻는 과정은 '최소한 이것 이상의 연산을 필요로 한다'라는, 최소로.. 더보기
최악의 경우와 평균 수행 시간 이론적인 분석 방법에서 평균 수행 시간을 측정하는 사실 어려운 일이다. 왜냐하면, 평균을 내기 위해서 측정해야 하는 환경을 항상 동일하게 유지하는 것은 힘든 일이고, 또 알고리즘의 입력값을 생각처럼 다양하게 지정할 수 없기 때문이다. 알고리즘의 수행 환경은 어느 정도 통제가 가능한 요소라고 할 수 있더라도, 입력값은 대체 어느 정도로 통제해야 하는지 결정하기 힘들다. 따라서, 알고리즘의 평균 수행 시간을 측정하기 위해서는 무엇보다 먼저 입력값에 대한 적절한 통계값이 있어야 한다. 즉, 입력으로 들어올 값이, 어떤 확률로 발생될 것인지 예측이 가능해야 입력값이 일정 정도 이상의 의미를 가질 수 있다는 의미이다. 최악의 경우는 평균 수행 시간 측정에 비해 분석하기가 수월하다. 입력값들에 대해서 가장 기대치가.. 더보기
알고리즘이란 무엇인가? 알고리즘이란, 문제를 해결하는 절차라고 할 수 있다. 하지만, 여기서 먼저 '문제가 무엇이냐'라는 것에 대해 명확한 정의가 있어야 한다. 이 문제가 해결이 가능한 문제인가? 불가능한 문제인가? 해결이 가능하다면 어느 정도까지 답을 얻을 수 있는가에 대한 정의가 있어야 명확한 문제라고 할 수 있다. 즉, 문제는 자신에게 어떤 값이 주어지고, 어떤 결과를 얻어야 할지가 분명해야 한다는 것이다. 또, 문제를 해결하는 것에 앞서서, 누가, 어떻게 문제를 해결할 것인지도 생각해야 한다. 여기서는, 문제를 해결하는 기본 바탕으로 RAM(Random Access Machine)이라는 기계를 생각하게 된다. 이 기계는 거의 무한대의 리소스와 CPU 파워를 가지고 있다고 하자. 이제, 여기서 문제의 답을 얻는 알고리즘을.. 더보기

티스토리툴바