About Lower Bound

Lower Bound of Algorithms

Q: “1ZB의 아이템을 정렬하고자하는 문제를 만났습니다.”

→ 동료가 이 정렬문제를 해결하고자 할 때, 전공자 입장에서 어떤 조언을 줄 것인가?

2가지 접근 방법이 있을 수 있다. 다루는 데이터의 크기가 매우 크므로,

1. 더욱 효율적인 알고리즘을 개발한다.
2. 더욱 효율적인 알고리즘은 불가능하다는 것을 증명하고, 그만두도록 한다.

Computational Complexity, Theory of computing, computation

→ “주어진 문제에 대하여, 모든 알고리즘의 효율성의 하한선 을 결정하라.”

Q: “하한선을 찾은 후에는?”(연구자 입장에서)

1. 새로운 디자인을 이용하여 더욱 효율적인 알고리즘을 찾으려고 시도한다.
2. 계산적 분석을 이용하여 더 나은 하한선을 찾으려고 노력한다.