문제의 복잡도를 알고, 문제를 해결할 알고리즘의 최악의 경우를 알고 있다고 하자. 해결 알고리즘의 최악의 경우를 W(n)이라 하고, 문제의 복잡도를 F(n)이라 했을 때, W(n) != F(n)이라면 2가지 결론을 얻을 수 있다. 첫째, 이 해결 알고리즘이 문제를 해결하는 최적의 알고리즘이 아닐 수도 있다는 것, 둘째, 그것이 아니라면 문제의 하한(lower bound)이 너무 낮게 잡혀있다는 것이다. 같지 않다고 해서 항상 해결 알고리즘이 최적의 알고리즘을 구현하지 못한 것은 아니다.
문제의 복잡도를 나타내는 하한(lower bound)는 더 높아질수록 현실적인 값이 된다. 반대로, 알고리즘은 상한(upper bound)에서 더 낮아질수록 더 좋은 알고리즘이 된다.
정렬된 입력값에 대해서, 어떤 값을 찾아내는 알고리즘을 생각해보자. 이 알고리즘은 처음부터 끝까지 입력값을 모두 검사하여 원하는 값을 찾는, 선형 시간을 소모하는 알고리즘이다. 즉, 입력값의 특성을 이용하지 않는 알고리즘이다. 여기에, 원하는 값을 찾았다면 그 시점에서 종료하도록 알고리즘을 수정했다고 하자. 그렇다면, 이 수정 사항은 얼마나 효율을 향상시킬 수 있는가?
최악의 경우는, 원하는 값이 마지막에 존재하는 경우이므로, 이 경우에는 수정 사항이 입력값의 특성과 무관하게 아무런 영향을 미치지 않는다. 따라서, 평균 수행 시간을 측정함으로써 알고리즘의 효율성 향상을 알아볼 수 있다.
<not complete>
Library/Algorithm