보간 탐색 ( Interpolation Search )

안녕하세요~~ 황금같은 주말 아침에 벌써 세번째 포스팅인것 같습니다.

이렇게 아침 시간을 이용해서 남들보다 더 부지런하게 뭔가 하다보면 나중엔 달콤한 상이 주어지게죠? ㅎㅎ

요즘 알고리즘을 다시 공부해 봐야 겠다는 생각에 여기저기 인터넷 서치해보면서 국내 및 해외 자료를 읽어보면서 

알고리즘 관련 자료를 찾아보고 포스팅을 하고 있는데요, 이번엔 보간 탐색 알고리즘에 대해서 포스팅하려 합니다. 

보간 탐색은 사실 제가 학교 다닐때는 못 배웠던 내용이었습니다. 그래서 알고리즘 이름부터가 생소했는데요

알고보니 이 녀석은 이진 탐색 알고리즘의 업그레이드 버전이라고 하더군요.

이진 탐색 알고리즘이 선형 알고리즘에 비해서 평균적으로 훨씬 빠른 시간복잡도를 가지고 있다고

지난 포스팅에서 말씀 드렸었는데요, 여기서 조금 더 빠르게 업그레이드 한 버전이 바로 이 보간 탐색입니다.

근데 이름이 너무 이상하네요, 차라리 그냥 영어로 인터폴레이션 탐색이라고 하는게 듣기에도 더 좋은 것 같은데요...

어쨌든, 보간(인터폴레이션) 탐색이라는 것은 이진 탐색에서 인덱스 구하는 공식을 조금 변형한 것입니다.

이진 탐색에서 다음에 조회할 인덱스 포인트를 조회하는 공식은 다음과 같았습니다.

mid = low + ( high - low ) / 2 

mid : 다음에 조회할 인덱스 포인트

low : 조회할 데이터 셋의 인덱스 중 가장 낮은 인덱스 포인트

high : 조회할 데이터 셋의 인덱스 중 가장 높은 인덱스 포인트

그런데 이렇게 하면 찾으려고자 하는 데이터와는 관계없이 무조건 중간에 위치한 인덱스를 검색하게 됩니다.

하지만 찾으려고자 하는 데이터와 조금이라도 더 가까운 인덱스를 찾을 수 있다면??? 

이런 생각에서부터 나온것이 바로 이 보간 탐색 알고리즘입니다.

보간 탐색 알고리즘에서 다음에 조회할 인덱스 포인트를 결정하는 방법은 아래와 같습니다.

이 계산법을 사용할 경우, 베스트 케이스 및 평균 시간 복잡도는  O(log (log n)) 이며,

이는 데이터셋의 요소(아이템)들이 적당히 균등한 간격으로 분포되어있다고 가정했을 때입니다.

[3,5,8,10,13,15] 처럼 2 또는 3 간격으로 분포되어있을 때가 한 예가 되겠네요.

그럼 최악의 경우 어떻게 될까요?

최악의 경우, 데이터 셋에 요소들이 균등하게 분포하지 않았다면 

 시간복잡도는 O(n) 을 보이게 됩니다. 선형 탐색과 다를 바가 없는 것이죠. 

예를 들면, [3,5,8,10,13,100] 처럼 불균등하게 분포가 되어있을 때가 그렇게 되겠죠.

자, 정리를 해보자면 보간 탐색 ( 인터폴레이션 탐색 ) 알고리즘은 

이진 탐색의 시간복잡도를 조금이나마 줄여보자는 의도로 만들어진 것이며

이진 탐색과 마찬가지로 정렬된 데이터 셋이 있을 때 사용합니다.

평균적으로 O( log ( log n ) )의 훌륭한 시간 복잡도를 보이나,

최악의 경우 ( 데이터 셋의 요소 분포가 불균등 한 경우 )에는 이진 탐색 보다 훨씬 느린

O (n) 의 시간 복잡도를 보인다는 것이 특징입니다.

자, 보간 탐색이라는 것이 뭔지 이해가 되시죠? 

간단히 말해서 이진 탐색 알고리즘의 업그레이드 버전이다~

라고 생각하시면 됩니다. ㅎㅎ

이제 외출 준비를 하러 가야겠습니다..

다들 좋은 하루 되시고 다음에 또 다른 알고리즘으로 찾아오겠습니다~~

좋은 하루 되세요~ ^-^