[Algorithm] Upper Bound, Lower Bound와 Optimal Algorithm

해결 가능한 어떤 문제가 주어져 있다고 했을 때, 이 문제를 해결하는 algorithm 의 upper bound 와 lower bound 를 어떻게 정의할 수 있을까요?

 

먼저 Upper Bound 에 대해 알아봅시다.

 

해결 가능한 어떤 문제를 T 시간 안에 해결하는 algorithm 이 존재한다. <=> 해당 문제를 해결하는 algorithm 의 upper bound 가 T 이다.

 

이 두 명제는 서로 동치입니다. 그렇다면, 의미없지만 당연한 예시로 size 가 n 인 array 를 sort 하는 문제는 O(n^100) 으로 해결할 수 있을 것이고, O(n^90) 으로도 해결할 수 있을 것입니다.

 

그렇기 때문에 Upper Bound 간 우열이 존재합니다. 더 짧은 시간 안에 문제를 해결하는 것이 우수하다고 생각하는 것이 자연스러우므로, 우수한 upper bound 는 소요 시간이 적은 것입니다.

 

Upper Bound 는 더 빠른 알고리즘이 존재할 수 있으므로, Big - Oh Notation 을 사용해서 표기하는 것이 보통입니다.

 

다음으로 Lower Bound 에 대해 알아봅시다.

 

어떤 가정 하에서 해결 가능한 어떤 문제를 T 시간보다 빨리 해결할 수 없다 <=> 해당 문제를 해결하는 alogorithm 의 lower bound 가 T이다. 

* 어떤 가정은 계산 모델, 추가 사용 공간 등 여러가지 제약 조건이 될 수 있습니다.

 

이 두 명제가 동치입니다.  마찬가지로 당연한 사례를 들며 lower bound 에 대해 이야기해보겠습니다. size 가 n 인 array 를 sort 하는 문제는 적어도 한 번의 비교는 필요할 것이므로 lower bound 가 Ω(1) 이라고 할 수 있습니다. 

 

하지만 이것은 큰 의미를 주지 못합니다. 따라서 lower bound 에도 우열이 존재하는데 lower bound 는 소요 시간이 더 길수록 우수한 lower bound 가 됩니다.

 

다음 그림을 보며 생각해보면 upper bound 와 lower bound 의 우열은 당연하게 결정됩니다.

 

이 알고리즘을 푸는 데 최소 이만큼은 걸린다 = lower bound, 이 알고리즘 푸는 데 이정도만 있으면 된다. = upper bound

 

이번에는 optimal algorithm 에 대해 이야기해보겠습니다.

 

optimal algorithm의 정의는 다음과 같습니다.

Optimal Algorithm: 어떤 문제를 해결하는 algorithm 의 upper bound 와 lower bound 가 일치한다면, 해당 upper bound 를 가진 algorithm 은 optimal algorithm 이 된다.

 

따라서 어떤 문제를 T시간 안에 해결하는 Optimal Algorithm 의 존재를 증명하는 방법은 다음과 같습니다.

1. T시간 안에 문제를 해결하는 algorithm 을 설계합니다. (upper bound)

2. Algorithm 의 lower bound 가 T임을 증명합니다. (lower bound)

-> 대부분 lower bound 를 증명하는 난이도가 높습니다.