中庸 中庸

해결 가능한 어떤 문제가 주어져 있다고 했을 때, 이 문제를 해결하는 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 간 우열이 존재합니다. 더 짧은 시간 안에 문제를 해결하는 것이 우수하다고 생각하..