Analysis of Algorithms | Lower and Upper Bound Theory

읽기 전

Lower와 Upper Bound의 개념을 정리하면서 많은 사람들이 상/하한과 상/하계라는 용어를 같이 쓰고 있어 혼란스러웠다. 다행히 두 개념을 구분해서 설명해주신 분을 찾아 해당 게시글의 내용을 참고하여 작성하였다.

• 상한(Supremum)과 하한(Infimum)

상계(Upper Bound) & 하계(Lower Bound)

상계란 실수 $b$가 집합 $A$의 모든 원소들보다 크거나 같을 때 즉, $a\in A$일 경우 $a\le b$ 이면 $b$를 집합 $A$의 상계(Upper bound)라 한다. 그리고 집합 A는 상계를 가지고 있으므로 위로 유계(bounded above)이다.

하계란 실수 $b$가 집합 $A$의 모든 원소들보다 작거나 같을 때 즉, $a\in A$일 경우 $a\ge b$ 이면 $b$를 집합 $A$의 하계(Lower bound)라 한다. 그리고 집합 A는 하계를 가지고 있으므로 아래로 유계(bounded below)이다.

집합 A의 상계와 하계 모두 존재하면 유계(bounded)라 한다.

위의 정의에서 우리는 상계와 하계는 유일하지 않다는 점을 알아낼 수 있다.

• Ex. 집합 $A = { x\in\mathbb{R} | -1 \le x＜ 2 }$의 상계와 하계의 범위를 작성해라.

  위 문제에서 A의 하계는 $x \le -1$인 모든 실수이고 상계는 $2 \le x$인 모든 실수이다.

상한(Supremum) & 하한(Infimum)

집합 $A$의 상계들의 집합을 $U$라 하면 $U$의 최소원소를 집합 $A$의 상한이라 하고 $\sup{A}$혹은 ⋁ $A$라 쓴다. 영어로 Least Upper Bound라 표현하고 상계 중 가장 작은 원소를 의미한다.

집합 $A$의 하계들의 집합을 $L$이라 하면 $L$의 최대원소를 집합 $A$의 하한이라 하고 $\inf{A}$ 혹은 ⋀ $B$라 쓴다. 영어로 Greatest Lower Bound라 표현하고 하계 중 가장 작은 원소를 의미한다.

무한집합에는 최대/최소 원소가 없을지라도 모든 집합(유,무한)에는 $\sup{A}$와 $\inf{A}$가 존재한다. 그리고 각각은 유일하다.

하계 이론(Lower Bound Theory)

알고리즘 $A(n)$에 대해 어떤 랜덤한 input을 넣었을 때 소요되는 시간이 $t(n)$보다 적을 순 없고 $A(n)$의 모든 연산은 최소한 $t(n)$ 이상의 시간을 가질 때 $t(n)$을 Lower Bound라 한다. 그리고 $t(n)$ 값을 계산할 수 있다면 실제 알고리즘의 복잡도와 비교하여 그것이 최선인지를 선언할 수 있다.

1. Trivial Lower Bound - input값과 output값을 기반으로 Lower Bound를 계산한다.

   예를들어 NxN 행렬 2개의 곱연산을 할 때, input은 $2n^2$개이고 ouput은 $n^2$이다. 이 경우 Lower Bound는 $O(n^2)$이다.

2. Calculating Lower Bound - 이진탐색트리와 같이 계산 가능한 경우

   n개의 원소에 대해 노드 수 $2^k-1$개의 트리를 구성했다고 가정하자.

   • 최악의 경우: n개의 원소에 대해 모두 비교한 경우이므로 $O(n)$
   • 최선의 경우: 각 tree level당 1번 비교한 경우이므로 $k\ge log_{2}{n}$에 따라 $O(log{n})$

$a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_1x+a_0$의 시간복잡도는?

일반적으로 $n+(n-1)+(n-2)+\cdots+2+1$이라고 생각하여 $O(n^2)$로 판단할 수 있다. (제곱계산*합계산) 그러나, 마지막부터 역순으로 점화식 형태를 유지하며 정리하면 $((\cdots(a_nx+a_{n-1})x+a_{n-2})x+\cdots)x+a_1)x+a_0$가 된다. 그러면 일반항은 $A=(A'+a_k)x$가 되는데 이 일반항을 $k=n$부터 $k=1$까지 돌린 후 마지막으로 $a_0$을 더하면 된다. 그러므로 시간복잡도는 $O(n)$이다.

상계 이론(Upper Bound Theory)

알고리즘의 상계를 $U(n)$라고 하자. 그러면 모든 경우의 계산에 대해 $U(n)$보다 적은 시간을 가지고 수행할 수 있음을 의미한다. 최악의 경우라도 수행 시간은 상계보다 작기 때문에 최적을 논하는 알고리즘에선 크게 의미를 갖지 못한다.

참고자료

1. Lower and Upper Bound Theory
2. 상한(Supremum)과 하한(Infimum)