[ Algorithm ] 파라메트릭 서치 ( Parametric Search )

Parametric Search 란?

최적화 문제 (문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제 ( decision problem )으로 바꾸어 푸는 것

 

파라메트릭 서치는 문제를 풀어나가는 과정이 바이너리 서치 ( 이분 탐색 ) 과 매우 흡사하다.

➡️ 의외의 문제들에 적용되어서 최적화 문제들을 조금 더 쉽게 풀 수 있게 해준다.

핵심은 결정 문제

           👉 해당값이 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야 최적화 문제를 파라메트릭 서치로 풀 수 있다.

           👉 정답이 될 수 있는 값들이 연속적이여야 파라메트릭 서치를 이용할 수 있다.

정답이 a일 때, a 이상의 값들은 모두 조건을 만족한다는 의미시간 복잡도

 

시간 복잡도

알고리즘 자체보다 조건 함수가 얼마나 빠른지에 달려있다. 맨 처음에 잡은 범위가 N 이라하면 루프는 logN 번 실행된다. 

즉, 조건 함수가 한 번 실행될 때 걸리는 시간복잡도를 O(C(n))이라고 하면, 총 시간 복잡도는 O(C(n)logM)이다.