PHP 순서 목록 검색 보간 검색 알고리즘의 단계에 대한 자세한 설명

이번에는 PHP 순서 테이블 검색 및 보간 검색 알고리즘의 단계에 대해 자세히 설명하겠습니다. PHP 순서 테이블 검색 및 보간 검색 알고리즘의 주의 사항은 무엇입니까?

서문:

앞서 이진 검색을 소개했는데, 생각해보면 왜 반으로 접어야 할까요? 4분의 1 이상으로 접는 것보다?

예를 들어 영어 사전에서 "사과"를 검색할 때 사전을 펼칠 때 무의식적으로 앞 페이지로 넘어가나요, 아니면 뒷 페이지로 넘어가나요? "동물원"을 다시 확인하면 어떻게 확인하나요? 당연히 사전의 중간부터 찾아보기 시작하는 것이 아니라, 어떤 목적을 가지고 앞이나 뒤를 바라봅니다.

마찬가지로, 예를 들어 0 ~ 10000 범위에서 작은 것부터 큰 것까지 균등하게 분포된 100개의 요소가 있는 배열에서 5를 찾으려면 자연스럽게 더 작은 배열 첨자를 먼저 고려하여 검색을 시작합니다.

위 분석은 실제로 이진 검색을 개선한 보간 검색 아이디어입니다.

기본 아이디어:

검색 방법은 검색할 키워드 키를 조회 테이블의 최대 및 최소 레코드의 키워드와 비교하는 것입니다. 그 핵심은 보간 계산 공식에 있습니다. 먼저 반탐색 계산식을 살펴보세요:

보간탐색은 1/2을 개선하여 다음 계산계획으로 변경합니다.

보간탐색 알고리즘의 핵심은 보간 계산 공식:

$num - $arr[$lower]
——————————————
$arr[$high] - $arr[$lower]

코드:

<?php //插值查找(前提是数组必须是有序数组) 事件复杂度　O(logn)
//但对于数组长度比较大，关键字分布又是比较均匀的来说，插值查找的效率比折半查找的效率高
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function insertsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //计数器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  // 折半查找 ： $middle = intval(($lower + $high) / 2);
  $middle = intval($lower + ($num - $arr[$lower]) / ($arr[$high] - $arr[$lower]) * ($high - $lower)); 
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = insertsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

요약:

시간 복잡도 관점에서 보면 O(logn)이지만 순서가 긴 목록과 상대적으로 고르게 분포된 조회 테이블의 경우 키워드, 보간 조회 알고리즘의 평균 성능은 좋은 키워드를 많이 찾기보다 두 배 높습니다. 반대로 배열 내 분포가 {0, 1, 2, 2000, 2001,. . . 999998, 999999} 보간 검색을 사용하는 이러한 종류의 매우 고르지 않은 데이터는 그다지 적합한 선택이 아닐 수 있습니다.

직접 예제를 만들었습니다:

$arr = array(0,1,2,2000,2001,2002,2003,2004,5555,69666,99999,100000);
echo "位置：".binsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;
$i = 0; //重置比较次数
echo "<br>";
echo "位置：".insertsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;

결과 출력:

位置：8
比较次数：2
位置：8
比较次数：9

매우 고르지 않은 데이터의 경우 보간 검색 효율성이 절반 검색보다 낮다는 것을 알 수 있습니다.

PS 기타 관련 기사가 온라인에 있습니다!

binsearch()추천 도서:

PHP 긴 연결 사용 사례 분석

PHP 데이터 내보내기 구현 방법

위 내용은 PHP 순서 목록 검색 보간 검색 알고리즘의 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!