Lower Bounds and the Complexity of Problems

 How can we show that an algorithm is optimal?

 - 우리는 어떤 알고리즘이 최적의 알고리즘이라는 것을 어떻게 증명할 수 있을까?

Do we have to analyze individually every other possible algorithm (including the ones we have not even thought of)?

 - 작동하는 모든 알고리즘들 (우리가 생각지도 못했던 것들 까지도)을 분석해야만 가능한걸까?

Fortunately, no; we can prove theorems that establish a lower bound on the number of operations needed to solve a problem.

 - 다행히도 그렇지않다. 우리는 문제를 풀기 위한 연산 횟수의 하한선을 설정함으로 다양한 정리(定理)들을 증명할 수 있다.

Then any algorithm that performs that number of operations would be optimal

 - 해당 연산 횟수에 작동되는 알고리즘이라면 모두 최적의 알고리즘이라고 할 수 있다.

Thus there are two tasks to be carried out in order to find a good algorithm, or, from another point of view, to answer the question

: How much work is necessary and sufficient to solve the problem?

 - 그러므로 좋은 알고리즘이라는 것을 판별하거나 해당 문제를 풀기 위한 적당한 연산의 수를 알아내기 위해서는 두가지 작업을 수행해야 한다.

1. Devise what seems to be an efficient algorithm; call it A. Analyze A and find a function W such that, for inputs of size n, A does at most W(n) steps in the worst case.

 -  1. 먼저 효율적인 알고리즘을 고안해라. 이것을 A라고 부르자. A를 분석하고 최악의 경우의  A알고리즘 연산 횟수를 구하는 함수를 만들어라.

2. For some function F, prove a theorem stating that, for any algorithm in the class under consideration, there is some input of size n for  which the algorithm must perform at least F(n) steps.

 - 2. 사료되는 문제를 해결하기 위한 최소한의 횟수를 구하는 함수 F가 옳음을 증명해라.

 If  the function W and F are equal, then the algorithm A is optimal (for the worst case). 

 - 만약 함수 W와  F가 같다면, 위 알고리즘 A는 최적의 알고리즘이다.(최악의 경우에 대해서)

If not, there may be a better algorithm or a better lower bound.

 - 그렇지 않다면, 더 나은 알고리즘이 있거나 더 낮은 하한선이 존재할 것이다.

An extract from 'Computer Algorithms -Introduction to Design and Analysis, Sara Baase, 2nd ed.'