보간법
보간법의 수학적 정의는 알고 있는 데이터 값들을 이용하여 모르는 값을 추정하는 방법의 한 종류이다.
종류에는 다항식 보간법, 스플라인 보간법 등이 있다.
실변수 x의 함수 f(x)의 모양은 미지이나, 어떤 간격(등간격이나 부등간격이나 상관없다)을 가지는 2개 이상인 변수의 값 xi(i＝1,2,…,n)에 대한 함수값 f(xi)가 알려져 있을 경우, 그 사이의 임의의 x에 대한 함수값을 추정하는 것을 말한다. 실험이나 관측에 의하여 얻은 관측값으로부터 관측하지 않은 점에서의 값을 추정하는 경우나 로그표 등의 함수표에서 표에 없는 함수값을 구하는 등의 경우에 이용된다. 가장 간단한 방법으로서는, 변수를 x좌표, 그 변수에 대한 기지 함수값을 y좌표로 하는 점들을 이어 곡선을 그어, 구하고자 하는 함수값을 구하는 방법이다.
[네이버 지식백과] 보간법 [interpolation, 補間法] (두산백과 두피디아, 두산백과)
선형 보간법(Linear Interpolation)
가장 간단한 방법으로 알고자 하는 함수가 직선의 함수라고 가정하고 함수값을 추정한다.
단순히 알려진 데이터 점들을 선형으로 이어주기만 하면 된다.
선형보간법은 쉽고 빠르지만 정확한 방법은 아니다.
다항식 보간법 (Polynomial Interpolation)
선형 보간법은 1차 방정식인 반면에 다항식 보간법은 2차 이상의 다항식을 가진다.
데이터의 점이 많을수록 다항식의 차수가 높아지므로 계산의 복잡성이 커진다.
데이터 점에 따라 다항식 자체가 많이 바뀌므로 제대로 된 보간을 기대하기 어렵다.
이러한 단점 때문에 스플라인 보간법을 이용한다.
스플라인 보간법(Spline Interpolation)
스플라인 보간법은 각 구간에서 낮은 차원의 다항식을 사용한다.
이 다항식은 앞/뒤 구간의 다항식들과 자연스럽게 연결될 수 있는 것으로 선택한다.
각 점에서 앞/뒤 스플라인 함수가 미분이 가능해야 하고 곡률도 같아야 한다.
보간 탐색
보간 탐색은 정렬된 리스트에서 범위를 줄여가며 검색하는 알고리즘입니다. 보간 검색은 전화번호부에서 이름
(책의 항목이 정렬되는 키 값)을 검색하는 방법과 유사합니다.
동작 방식은 이진 탐색과 비슷하지만 탐색 위치를 정하는 방식이 다릅니다.
탐색 위치
위 그림은 검색 값 3을 찾을 때 첫 번째 탐색 위치를 보여줍니다.
이진 탐색은 항상 중간 위치로 탐색 위치를 결정합니다.
반면에 보간 탐색은 검색키 값에 따라 다른 위치로 이동하게 됩니다. 예를 들어 검색 값이 상대적으로 앞에 있다고 판단하면 앞쪽에서 탐색을 진행합니다.
데이터가 선형으로 분포되어 있으면 위에 그림과 같이 보간 탐색은 한 번에 데이터를 찾기도 합니다.
이처럼 보간 탐색은 데이터가 선형으로 분포되어 있을수록 검색 효율이 좋습니다.
선형으로 분포되어있다는 말은 데이터가 인덱스 값에 비례한다는 의미입니다.
동작 방식
보간 탐색은 정렬된 배열에서만 사용할 수 있고 이진 탐색과 동작 방식은 같습니다.
탐색 위치(pos)를 가져옵니다.
탐색 위치에 있는 값과 검색 값을 비교합니다.
값이 같다면(arr[pos] == key) 종료합니다.
검색 값이 크다면(arr[pos] < key) 탐색 위치 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (low = pos+1)
검색 값이 작다면(arr[pos] > key) 탐색 위치 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (high = pos-1)
값을 찾거나 간격이 비어있을 때까지 반복합니다.
