binary search1 Binary Search 정리, 이해 및 예제 개념 [Concept] 수학에서 정확한 해를 구할 수 없는 문제의 근사해를 구하기 위해 사용되는 이분법(Bisection Method)이 Computer Science의 Bineary Search 와 매우 유사하다. Case 1 - Linear 한(즉, O(N)이 걸리는) 알고리즘으로는 해결이 불가능한 경우. Binary Search 기법을 이용하여, $ O(log_{2}N) $ 의 시간 복잡도를 얻을 수 있다. Case 2 - 자명한 해를 구할 수 없고, 주어진 허용 오차 안에서 근사해를 구해야 하는 경우. 구간 $ [low, high] $ 안에서 어떠한 조건을 만족하는 해를 구한다고 하자. 해가 범위 안에 무조건 존재한다고 가정하면, 첫 수행에 발생 가능한 최대 오차는 $ |high-low| $ 이다.. 2021. 2. 16. 이전 1 다음
